blob: f8193d07e384fcc756e54894db14e074b2951957 (
plain) (
blame)
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
|
.TH ZPTEST 3 libzahl
.SH NAME
zptest - Test the primality of a big integer
.SH SYNOPSIS
.nf
#include <zahl.h>
enum zprimality zptest(z_t \fIwitness\fP, z_t \fIquestioned\fP, z_t \fItries\fP);
.fi
.SH DESCRIPTION
.B zptest
tests whether
.I questioned
is a prime number. This is implemented using the
Miller–Rabin primality test.
.P
If
.I questioned
is determined to be a composite, the witness if its
compositeness is stored into
.I witness
unless
.I witness
is
.BR 0 .
.BR zgcd (3)
can be used on
.I questioned
and
.I witness
to extract a factor of
.IR questioned .
This factor can be either composite, prime, or 1.
.P
The risk that a composite number is determined to be
a probably prime is
.IR (1-4↑-tries) .
.P
It is safe to call
.B zptest
with non-unique parameters, and with
.IR "(witness==0)" .
.SH RETURN VALUE
This function will either return:
.TP
.B NONPRIME
.I questioned
is certainly a composite number.
.TP
.B PROBABLY_PRIME
.I questioned
is probably a prime number.
.TP
.B PRIME
.I questioned
is certainly a prime number.
.SH NOTES
If
.I questioned
is less than two
.I questioned
is copied into
.P
Increasing
.I tries
only reduces the chance that
.B PROBABLY_PRIME
is returned. It cannot increase
the chance that
.B PRIME
is returned.
.IR witness .
.SH SEE ALSO
.BR zgcd (3)
|
