Some information about PrimeQ function

Question

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.

Answer 1

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.

Answer 2

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