1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
--- status: Draft
--- author(s): Gregory G. Smith
--- notes:
-- in PrimaryDecomposition: (isPrime, Ideal)
doc ///
Key
(isPseudoprime,ZZ)
isPseudoprime
Headline
whether an integer is probably prime
Usage
isPseudoprime x
Inputs
x:ZZ
Outputs
:Boolean
Description
Text
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 @ TO "FLINT" @ library.
Example
n = 1166513229502037
isPseudoprime n
isPrime n
n1 = nextPrime(n+1)
factor(n1^2*n)
Text
These functions handle numbers larger than this. For example,
Example
m = 158174196546819165468118574681196546811856748118567481185669501856749
isPseudoprime m
isPrime m
isPrime m^2
factor m^2
Example
ndigits = 30
m = nextPrime(10^30)
m1 = nextPrime (m+10^10)
m2 = nextPrime (m1 + 10^20)
isPrime m
isPrime m1
isPrime (m*m1)
isPrime(m*m*m1*m1*m2^6)
elapsedTime facs = factor(m*m1)
facs = facs//toList/toList
assert(set facs === set {{m,1}, {m1,1}})
m3 = nextPrime (m^3)
elapsedTime isPrime m3
elapsedTime isPseudoprime m3
SeeAlso
(isPrime,ZZ)
(factor,ZZ)
(nextPrime,Number)
///
document {
Key => {isPrime, (isPrime, ZZ), (isPrime, RingElement)},
Headline => "whether a integer or polynomial is prime",
Usage => "isPrime f",
Inputs => {
"f" => {ofClass ZZ, ", or an element in a ", TO2("PolynomialRing", "polynomial ring")}
},
Outputs => {
Boolean => {TO "true", " if ", TT "f", " is either a prime integer or an irreducible polynomial and ",
TO "false", " otherwise"}
},
EXAMPLE lines ///
ZZ/2[t];
isPrime(t^2+t+1)
isPrime(t^2+1)
isPrime 101
isPrime 158174196546819165468118574681196546811856748118567481185669501856749
isPrime 158174196546819165468118574681196546811856748118567481185669501856749^2
///,
PARA {
"Since ", TO "factor", " returns factors guaranteed only to be pseudoprimes, it
may be useful to check their primality, as follows."
},
EXAMPLE lines ///
f = factor 28752093487520394720397634653456
peek'_2 f
first \ toList f
isPrime \ oo
///,
PARA {
"Primality testing for integers is handled by ", TO "FLINT", "."
},
SeeAlso => {factor, isPseudoprime, "MinimalPrimes :: isPrime(Ideal)"}
}
|
