In my laptop for 200 digit numbers
sage: time p=next_prime(10^200)
CPU times: user 1.04 s, sys: 591 µs, total: 1.04 s
Wall time: 1.04 s
sage: time p=next_probable_prime(10^200)
CPU times: user 20.7 ms, sys: 0 ns, total: 20.7 ms
Wall time: 21.8 ms
What return exacty next_probable_prime? When is desired to use it?
The next_prime function relies on nextprime from PARI, which finds the next pseudoprimenumber as defined on the page https://pari.math.u-bordeaux.fr/docht...
A prime number is pseudoprime and "most" non-prime numbers are not pseudoprime. The benefit of such function is, as you noticed, checking that a number is pseudoprime is much faster than checking that a number is prime.
According to the Sage doc, by default next_prime proves that the returned number is actually a prime number, which is not the case for next_probable_prime, though no example of a probable prime that is not a genuine prime was found yet (according to the doc), and no such number $\leq 2^{64}$ exist.
Asked: 2020-11-28 18:53:50 +0100
Seen: 509 times
Last updated: Nov 30 '20
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
