Ask Your Question

Revision history [back]

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.