# Some information about PrimeQ function

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.

• 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.