Ask Your Question

# Loop is not finishing execution

I have the following Sage code:

p1 = 2
p2 = 5
e1 = ceil(100*log(2,p1))
e2 = ceil(5060*log(2,p2))
f = 1
p = p1^e1*p2^e2-1
while p not in Primes():
f = f + 1
p = p1^e1*p2^e2*f-1
p


I'm running this code in Sage Notebook, in a cell, but the value of p is never printed. I guess it is not finishing the execution. If I run the same code in Magma, it finishes after few seconds with the result of p. Any ideas what the problem might be?

edit retag close merge delete

## 1 answer

Sort by ยป oldest newest most voted

An alternative is to use pseudo-primality testing

sage: while not p.is_prime(proof=False):
....:     f = f + 1
....:     p = p1^e1 * p2^e2 * f - 1
sage: f
356


Note that a primality certificate for the number p above might be hard to produce and Sage currently does not know. The following is likely to run forever

sage: p = p1^e1 * p2^e2 * 356 - 1
sage: p.is_prime()     # be ready to wait


I have no idea whether Magma has optimized some primality testing for numbers of the form n - 1 or n + 1 with a simple factorization of n or whether they are actually doing pseudo-primality testing.

more

## Comments

Thank you, this worked nicely. I also don't know how Magma handles primality testing, but probably they do pseudo-primality testing.

( 2017-11-14 07:24:17 -0600 )edit

Great! This is why I am using Sage: I know how it works (or I can look at it) :-) If you are satisfied with the answer, could you accept it so that the question appears as "answered" (tick box on the left)?

( 2017-11-14 08:37:10 -0600 )edit

Ops sorry, had forgot to accept it. Just did! Thanks once again.

( 2017-11-14 09:46:07 -0600 )edit

## Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

## Stats

Asked: 2017-11-14 02:39:45 -0600

Seen: 55 times

Last updated: Nov 14 '17