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

Synopsis

Function: isPseudoprime
Usage:

isPseudoprime x
Inputs:
- x, an integer,
Outputs:
- a Boolean value,

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)
 -- 5.2914 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.0476394 seconds elapsed

o23 = true

i24 : elapsedTime isPseudoprime m3
 -- 0.000114459 seconds elapsed

o24 = true

Ways to use this method: