Ask Your Question

What is next_probable_prime ?

asked 2020-11-28 18:53:50 +0200

Andr gravatar image

updated 2020-11-28 19:02:56 +0200

FrédéricC gravatar image

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?

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2020-11-28 19:12:14 +0200

tmonteil gravatar image

updated 2020-11-30 15:41:36 +0200

The next_prime function relies on nextprime from PARI, which finds the next pseudoprimenumber as defined on the page

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.

edit flag offensive delete link more


Both next_prime and next_probable_prime uses probabilistic but next_prime is exhausted and next_probable_prime has reasonable limitations of reliability?

Andr gravatar imageAndr ( 2020-11-28 19:22:24 +0200 )edit

I edited my answer to be more precise (last paragraph).

tmonteil gravatar imagetmonteil ( 2020-11-28 20:25:29 +0200 )edit

Your Answer

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

Add Answer

Question Tools

1 follower


Asked: 2020-11-28 18:53:50 +0200

Seen: 422 times

Last updated: Nov 30 '20