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)