diff options
Diffstat (limited to 'src/libsec/port/probably_prime.c')
| -rw-r--r-- | src/libsec/port/probably_prime.c | 28 |
1 files changed, 14 insertions, 14 deletions
diff --git a/src/libsec/port/probably_prime.c b/src/libsec/port/probably_prime.c index 4eaccbad..beb03251 100644 --- a/src/libsec/port/probably_prime.c +++ b/src/libsec/port/probably_prime.c @@ -2,10 +2,10 @@ #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 +/* 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) { @@ -19,18 +19,18 @@ probably_prime(mpint *n, int nrep) nrep = 18; k = mptoi(n); - if(k == 2) // 2 is prime + if(k == 2) /* 2 is prime */ return 1; - if(k < 2) // 1 is not prime + if(k < 2) /* 1 is not prime */ return 0; - if((n->p[0] & 1) == 0) // even is not prime + if((n->p[0] & 1) == 0) /* even is not prime */ return 0; - // test against small prime numbers + /* test against small prime numbers */ if(smallprimetest(n) < 0) return 0; - // fermat test, 2^n mod n == 2 if p is prime + /* fermat test, 2^n mod n == 2 if p is prime */ x = uitomp(2, nil); y = mpnew(0); mpexp(x, n, n, y); @@ -43,21 +43,21 @@ probably_prime(mpint *n, int nrep) nbits = mpsignif(n); nm1 = mpnew(nbits); - mpsub(n, mpone, nm1); // nm1 = n - 1 */ + mpsub(n, mpone, nm1); /* nm1 = n - 1 */ k = mplowbits0(nm1); q = mpnew(0); - mpright(nm1, k, q); // q = (n-1)/2**k + mpright(nm1, k, q); /* q = (n-1)/2**k */ for(rep = 0; rep < nrep; rep++){ - // x = random in [2, n-2] + /* 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 + /* y = x**q mod n */ mpexp(x, q, n, y); if(mpcmp(y, mpone) == 0 || mpcmp(y, nm1) == 0) @@ -65,7 +65,7 @@ probably_prime(mpint *n, int nrep) for(j = 1; j < k; j++){ mpmul(y, y, x); - mpmod(x, n, y); // y = y*y mod n + mpmod(x, n, y); /* y = y*y mod n */ if(mpcmp(y, nm1) == 0) goto done; if(mpcmp(y, mpone) == 0){ |