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$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .