# isPseudoprime(ZZ) -- whether an integer is probably prime

## Description

Performs some trial division and then some probabilistic primality tests. If $x$ is definitely composite, the function returns false, otherwise it is declared probably prime, i.e. prime for most practical purposes, and the function returns true. The chance of declaring a composite number prime is very small. Subsequent calls to the same function do not increase the probability of the number being prime. In fact, there are no known numbers which are composite, and for which this function returns true, although it is expected that there are an infinite number of such primes.

This function calls a function in the FLINT library.

 i1 : n = 1166513229502037 o1 = 1166513229502037 i2 : isPseudoprime n o2 = true i3 : isPrime n o3 = true i4 : n1 = nextPrime(n+1) o4 = 1166513229502141 i5 : factor(n1^2*n) 2 o5 = 1166513229502037*1166513229502141 o5 : Expression of class Product

These functions handle numbers larger than this. For example,

 i6 : m = 158174196546819165468118574681196546811856748118567481185669501856749 o6 = 158174196546819165468118574681196546811856748118567481185669501856749 i7 : isPseudoprime m o7 = true i8 : isPrime m o8 = true i9 : isPrime m^2 o9 = false i10 : factor m^2 2 o10 = 158174196546819165468118574681196546811856748118567481185669501856749 o10 : Expression of class Product
 i11 : ndigits = 30 o11 = 30 i12 : m = nextPrime(10^30) o12 = 1000000000000000000000000000057 i13 : m1 = nextPrime (m+10^10) o13 = 1000000000000000000010000000083 i14 : m2 = nextPrime (m1 + 10^20) o14 = 1000000000100000000010000000229 i15 : isPrime m o15 = true i16 : isPrime m1 o16 = true i17 : isPrime (m*m1) o17 = false i18 : isPrime(m*m*m1*m1*m2^6) o18 = false i19 : elapsedTime facs = factor(m*m1) -- 14.2689 seconds elapsed o19 = 1000000000000000000000000000057*1000000000000000000010000000083 o19 : Expression of class Product i20 : facs = facs//toList/toList o20 = {{1000000000000000000000000000057, 1}, ----------------------------------------------------------------------- {1000000000000000000010000000083, 1}} o20 : List i21 : assert(set facs === set {{m,1}, {m1,1}}) i22 : m3 = nextPrime (m^3) o22 = 10000000000000000000000000001710000000000000000000000000097470000000000 00000000000000185613 i23 : elapsedTime isPrime m3 -- 0.12882 seconds elapsed o23 = true i24 : elapsedTime isPseudoprime m3 -- 0.000341395 seconds elapsed o24 = true