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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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