# 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

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

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

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)?

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