3
$\begingroup$

In Mathematica there is a built-in function called PrimeQ which tests given input as True or False. How that PrimeQ function ? which primality test is used so that so efficient for numbers of or more 1000 digits.

$\endgroup$

2 Answers 2

11
$\begingroup$

Source: https://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html

  • PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test.

  • As of 1997, this procedure is known to be correct only for $n<10^{16}$, and it is conceivable that for larger it could claim a
    composite number to be prime.

  • The Primality Proving Package contains a much slower algorithm that has been proved correct for all . It can return an explicit
    certificate of primality.

This algorithm is also know as a variant of Baillie-PSW primality Test

Though Mathematica says approximatly $10^{16}$ as the upper border, newer sources claim this border 3 magnitudes higher to be about $1.8\cdot 10^{19}=2^{64}$. But you don't have to worry that you'll find a false-positive. This is unbelievable unlikely.

$\endgroup$
1
$\begingroup$

Since rather recently in version 13 PrimeQ is using updated Baillie-PSW from this new paper from Baillie himself, so not only needless base 3 Miller-Rabin is removed, but it may now be faster than even GMP: https://arxiv.org/abs/2006.14425

Was confirmed by @daniel-lichtblau in https://community.wolfram.com/groups/-/m/t/2898096

Nice to see Baillie participating too here on stack: https://crypto.stackexchange.com/questions/103085/why-does-gmp-only-run-miller-rabin-test-twice-when-generating-a-prime/103896#103896

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.