Macaulay2 » Documentation
Packages » Macaulay2Doc :: isPseudoprime(ZZ)
next | previous | forward | backward | up | index | toc

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

Synopsis

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.08868s 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
 -- .0483693s elapsed

o23 = true
i24 : elapsedTime isPseudoprime m3
 -- .000114371s elapsed

o24 = true

See also

Ways to use this method: