zptest.3 - libzahl - big integer library
 (HTM) git clone git://git.suckless.org/libzahl
 (DIR) Log
 (DIR) Files
 (DIR) Refs
 (DIR) README
 (DIR) LICENSE
       ---
       zptest.3 (1512B)
       ---
            1 .TH ZPTEST 3 libzahl
            2 .SH NAME
            3 zptest - Test the primality of a big integer
            4 .SH SYNOPSIS
            5 .nf
            6 #include <zahl.h>
            7 
            8 enum zprimality zptest(z_t \fIwitness\fP, z_t \fIquestioned\fP, int \fItries\fP);
            9 .fi
           10 .SH DESCRIPTION
           11 .B zptest
           12 tests whether
           13 .I questioned
           14 is a prime number. This is implemented using the
           15 Miller–Rabin primality test.
           16 .P
           17 If
           18 .I questioned
           19 is determined to be a composite, the witness if its
           20 compositeness is stored into
           21 .I witness
           22 unless
           23 .I witness
           24 is
           25 .BR 0 .
           26 .BR zgcd (3)
           27 can be used on
           28 .I questioned
           29 and
           30 .I witness
           31 to extract a factor of
           32 .IR questioned .
           33 This factor can be either composite, prime, or 1.
           34 .P
           35 The risk that a composite number is determined to be
           36 a probably prime is
           37 .IR (1-4↑-tries) .
           38 .P
           39 It is safe to call
           40 .B zptest
           41 with non-unique parameters, and with
           42 .IR "(witness==0)" .
           43 .SH RETURN VALUE
           44 This function will either return:
           45 .TP
           46 .B NONPRIME
           47 .I questioned
           48 is certainly a nonprime number (composite).
           49 .TP
           50 .B PROBABLY_PRIME
           51 .I questioned
           52 is probably a prime number.
           53 .TP
           54 .B PRIME
           55 .I questioned
           56 is certainly a prime number.
           57 .SH NOTES
           58 If
           59 .I questioned
           60 is less than two
           61 .I questioned
           62 is copied into
           63 .P
           64 Increasing
           65 .I tries
           66 only reduces the chance that
           67 .B PROBABLY_PRIME
           68 is returned. It cannot increase
           69 the chance that
           70 .B PRIME
           71 is returned.
           72 .IR witness .
           73 .SH RATIONALE
           74 .B NONPRIME
           75 is called just that, rather than COMPOSITE,
           76 because negative integers, zero, and one are
           77 neither prime nor composite. (One was historically
           78 a prime, we do not recognise it as such.)
           79 .SH SEE ALSO
           80 .BR zgcd (3)