ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 28 Nov 2020 20:25:29 +0100What is next_probable_prime ?https://ask.sagemath.org/question/54422/what-is-next_probable_prime/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?Sat, 28 Nov 2020 18:53:50 +0100https://ask.sagemath.org/question/54422/what-is-next_probable_prime/Answer by tmonteil for <p>In my laptop for 200 digit numbers</p>
<pre><code>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
</code></pre>
<p>What return exacty next_probable_prime? When is desired to use it?</p>
https://ask.sagemath.org/question/54422/what-is-next_probable_prime/?answer=54423#post-id-54423The `next_prime` function relies on `nextprime` from `PARI`, which finds the next *pseudoprime* number as defined on the page https://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#se:ispseudoprime
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.Sat, 28 Nov 2020 19:12:14 +0100https://ask.sagemath.org/question/54422/what-is-next_probable_prime/?answer=54423#post-id-54423Comment by Andr for <p>The <code>next_prime</code> function relies on <code>nextprime</code> from <code>PARI</code>, which finds the next <em>pseudoprime</em>number as defined on the page <a href="https://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#se:ispseudoprime">https://pari.math.u-bordeaux.fr/docht...</a></p>
<p>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.</p>
<p>According to the Sage doc, by default <code>next_prime</code> <em>proves</em> that the returned number is actually a prime number, which is not the case for <code>next_probable_prime</code>, 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.</p>
https://ask.sagemath.org/question/54422/what-is-next_probable_prime/?comment=54424#post-id-54424Both next_prime and next_probable_prime uses probabilistic but next_prime is exhausted and next_probable_prime has reasonable limitations of reliability?Sat, 28 Nov 2020 19:22:24 +0100https://ask.sagemath.org/question/54422/what-is-next_probable_prime/?comment=54424#post-id-54424Comment by tmonteil for <p>The <code>next_prime</code> function relies on <code>nextprime</code> from <code>PARI</code>, which finds the next <em>pseudoprime</em>number as defined on the page <a href="https://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#se:ispseudoprime">https://pari.math.u-bordeaux.fr/docht...</a></p>
<p>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.</p>
<p>According to the Sage doc, by default <code>next_prime</code> <em>proves</em> that the returned number is actually a prime number, which is not the case for <code>next_probable_prime</code>, 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.</p>
https://ask.sagemath.org/question/54422/what-is-next_probable_prime/?comment=54426#post-id-54426I edited my answer to be more precise (last paragraph).Sat, 28 Nov 2020 20:25:29 +0100https://ask.sagemath.org/question/54422/what-is-next_probable_prime/?comment=54426#post-id-54426