diff options
| -rw-r--r-- | include/version.h | 2 | ||||
| -rw-r--r-- | libsec/port/probably_prime.c | 59 |
2 files changed, 33 insertions, 28 deletions
diff --git a/include/version.h b/include/version.h index 970d0575..847a6e5b 100644 --- a/include/version.h +++ b/include/version.h @@ -1 +1 @@ -#define VERSION "Fourth Edition (20100305)" +#define VERSION "Fourth Edition (20100307)" diff --git a/libsec/port/probably_prime.c b/libsec/port/probably_prime.c index 4eaccbad..93fdebf0 100644 --- a/libsec/port/probably_prime.c +++ b/libsec/port/probably_prime.c @@ -9,7 +9,7 @@ int probably_prime(mpint *n, int nrep) { - int j, k, rep, nbits, isprime = 1; + int j, k, rep, nbits, isprime; mpint *nm1, *q, *x, *y, *r; if(n->sign < 0) @@ -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,38 +43,43 @@ 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] - r = mprand(nbits, prng, nil); - mpmod(r, nm1, x); - mpfree(r); - if(mpcmp(x, mpone) <= 0) - continue; + for(;;){ + /* find x = random in [2, n-2] */ + r = mprand(nbits, prng, nil); + mpmod(r, nm1, x); + mpfree(r); + if(mpcmp(x, mpone) > 0) + break; + } - // y = x**q mod n + /* y = x**q mod n */ mpexp(x, q, n, y); if(mpcmp(y, mpone) == 0 || mpcmp(y, nm1) == 0) - goto done; + continue; - 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; - } + for(j = 1;; j++){ + if(j >= k) { + isprime = 0; + goto done; + } + mpmul(y, y, x); + mpmod(x, n, y); /* y = y*y mod n */ + if(mpcmp(y, nm1) == 0) + break; + if(mpcmp(y, mpone) == 0){ + isprime = 0; + goto done; + } } - isprime = 0; } + isprime = 1; done: mpfree(y); mpfree(x); |