libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | 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)