1 | initial version |
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.