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
|
#include "os.h"
#include <mp.h>
#include <libsec.h>
// Miller-Rabin probabilistic primality testing
// Knuth (1981) Seminumerical Algorithms, p.379
// Menezes et al () Handbook, p.39
// 0 if composite; 1 if almost surely prime, Pr(err)<1/4**nrep
int
probably_prime(mpint *n, int nrep)
{
int j, k, rep, nbits, isprime = 1;
mpint *nm1, *q, *x, *y, *r;
if(n->sign < 0)
sysfatal("negative prime candidate");
if(nrep <= 0)
nrep = 18;
k = mptoi(n);
if(k == 2) // 2 is prime
return 1;
if(k < 2) // 1 is not prime
return 0;
if((n->p[0] & 1) == 0) // even is not prime
return 0;
// test against small prime numbers
if(smallprimetest(n) < 0)
return 0;
// fermat test, 2^n mod n == 2 if p is prime
x = uitomp(2, nil);
y = mpnew(0);
mpexp(x, n, n, y);
k = mptoi(y);
if(k != 2){
mpfree(x);
mpfree(y);
return 0;
}
nbits = mpsignif(n);
nm1 = mpnew(nbits);
mpsub(n, mpone, nm1); // nm1 = n - 1 */
k = mplowbits0(nm1);
q = mpnew(0);
mpright(nm1, k, q); // q = (n-1)/2**k
for(rep = 0; rep < nrep; rep++){
// x = random in [2, n-2]
r = mprand(nbits, prng, nil);
mpmod(r, nm1, x);
mpfree(r);
if(mpcmp(x, mpone) <= 0)
continue;
// y = x**q mod n
mpexp(x, q, n, y);
if(mpcmp(y, mpone) == 0 || mpcmp(y, nm1) == 0)
goto done;
for(j = 1; j < k; j++){
mpmul(y, y, x);
mpmod(x, n, y); // y = y*y mod n
if(mpcmp(y, nm1) == 0)
goto done;
if(mpcmp(y, mpone) == 0){
isprime = 0;
goto done;
}
}
isprime = 0;
}
done:
mpfree(y);
mpfree(x);
mpfree(q);
mpfree(nm1);
return isprime;
}
|