X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/87b63d41842c25ce787391cf5f9e262dad449bd3..cc3ca08f22460b15423bb88632f3a12741b19003:/pfilt.c diff --git a/pfilt.c b/pfilt.c index eda5116..ae99a9b 100644 --- a/pfilt.c +++ b/pfilt.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: pfilt.c,v 1.2 2000/06/17 11:54:27 mdw Exp $ + * $Id: pfilt.c,v 1.6 2004/04/08 01:36:15 mdw Exp $ * * Finding and testing prime numbers * * (c) 1999 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,47 +15,98 @@ * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. - * + * * Catacomb is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Library General Public License for more details. - * + * * You should have received a copy of the GNU Library General Public * License along with Catacomb; if not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* +/*----- Header files ------------------------------------------------------*/ + +#include "mp.h" +#include "mpint.h" +#include "pfilt.h" +#include "pgen.h" +#include "primetab.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @smallenough@ --- * * - * $Log: pfilt.c,v $ - * Revision 1.2 2000/06/17 11:54:27 mdw - * Use new MP memory management functions. + * Arguments: @mp *m@ = integer to test * - * Revision 1.1 1999/12/22 15:49:39 mdw - * Renamed from `pgen'. Reworking for new prime-search system. + * Returns: One of the @PGEN@ result codes. * - * Revision 1.3 1999/12/10 23:28:35 mdw - * Track suggested destination changes. + * Use: Assuming that @m@ has been tested by trial division on every + * prime in the small-primes array, this function will return + * @PGEN_DONE@ if the number is less than the square of the + * largest small prime. + */ + +static int smallenough(mp *m) +{ + static mp *max = 0; + int rc = PGEN_TRY; + + if (!max) { + max = mp_fromuint(MP_NEW, MAXPRIME); + max = mp_sqr(max, max); + max->a->n--; /* Permanent allocation */ + } + if (MP_CMP(m, <=, MP_ONE)) + rc = PGEN_FAIL; + else if (MP_CMP(m, <, max)) + rc = PGEN_DONE; + return (rc); +} + +/* --- @pfilt_smallfactor@ --- * * - * Revision 1.2 1999/11/20 22:23:05 mdw - * Add multiply-and-add function for Diffie-Hellman safe prime generation. + * Arguments: @mp *m@ = integer to test * - * Revision 1.1 1999/11/19 13:17:57 mdw - * Prime number generator and tester. + * Returns: One of the @PGEN@ result codes. * + * Use: Tests a number by dividing by a number of small primes. This + * is a useful first step if you're testing random primes; for + * sequential searches, @pfilt_create@ works better. */ -/*----- Header files ------------------------------------------------------*/ +int pfilt_smallfactor(mp *m) +{ + int rc = PGEN_TRY; + int i; + size_t sz = MP_LEN(m); + mparena *a = m->a ? m->a : MPARENA_GLOBAL; + mpw *v = mpalloc(a, sz); -#include "mp.h" -#include "mpmont.h" -#include "pfilt.h" -#include "pgen.h" -#include "primetab.h" + /* --- Fill in the residues --- */ -/*----- Main code ---------------------------------------------------------*/ + for (i = 0; i < NPRIME; i++) { + if (!mpx_udivn(v, v + sz, m->v, m->vl, primetab[i])) { + if (MP_LEN(m) == 1 && m->v[0] == primetab[i]) + rc = PGEN_DONE; + else + rc = PGEN_FAIL; + break; + } + } + + /* --- Check for small primes --- */ + + if (rc == PGEN_TRY) + rc = smallenough(m); + + /* --- Done --- */ + + mpfree(a, v); + return (rc); +} /* --- @pfilt_create@ --- * * @@ -74,9 +125,9 @@ int pfilt_create(pfilt *p, mp *m) { int rc = PGEN_TRY; int i; - mp *r = MP_NEW; - mpw qw; - mp q; + size_t sz = MP_LEN(m); + mparena *a = m->a ? m->a : MPARENA_GLOBAL; + mpw *v = mpalloc(a, sz); /* --- Take a copy of the number --- */ @@ -85,11 +136,8 @@ int pfilt_create(pfilt *p, mp *m) /* --- Fill in the residues --- */ - mp_build(&q, &qw, &qw + 1); for (i = 0; i < NPRIME; i++) { - qw = primetab[i]; - mp_div(0, &r, m, &q); - p->r[i] = r->v[0]; + p->r[i] = mpx_udivn(v, v + sz, m->v, m->vl, primetab[i]); if (!p->r[i] && rc == PGEN_TRY) { if (MP_LEN(m) == 1 && m->v[0] == primetab[i]) rc = PGEN_DONE; @@ -98,9 +146,14 @@ int pfilt_create(pfilt *p, mp *m) } } + /* --- Check for small primes --- */ + + if (rc == PGEN_TRY) + rc = smallenough(m); + /* --- Done --- */ - mp_drop(r); + mpfree(a, v); return (rc); } @@ -155,11 +208,10 @@ int pfilt_step(pfilt *p, mpw step) } } - /* --- Small numbers must be prime --- */ + /* --- Check for small primes --- */ - if (rc == PGEN_TRY && MP_LEN(p->m) == 1 && - p->m->v[0] < MAXPRIME * MAXPRIME) - rc = PGEN_DONE; + if (rc == PGEN_TRY) + rc = smallenough(p->m); /* --- Done --- */ @@ -202,7 +254,7 @@ int pfilt_muladd(pfilt *p, const pfilt *q, mpw m, mpw a) } /* --- Gallivant through the residue table --- */ - + for (i = 0; i < NPRIME; i++) { p->r[i] = (q->r[i] * m + a) % primetab[i]; if (!p->r[i] && rc == PGEN_TRY) { @@ -213,11 +265,10 @@ int pfilt_muladd(pfilt *p, const pfilt *q, mpw m, mpw a) } } - /* --- Small numbers must be prime --- */ + /* --- Check for small primes --- */ - if (rc == PGEN_TRY && MP_LEN(p->m) == 1 && - p->m->v[0] < MAXPRIME * MAXPRIME) - rc = PGEN_DONE; + if (rc == PGEN_TRY) + rc = smallenough(p->m); /* --- Finished --- */ @@ -265,11 +316,10 @@ int pfilt_jump(pfilt *p, const pfilt *j) } } - /* --- Small numbers must be prime --- */ + /* --- Check for small primes --- */ - if (rc == PGEN_TRY && MP_LEN(p->m) == 1 && - p->m->v[0] < MAXPRIME * MAXPRIME) - rc = PGEN_DONE; + if (rc == PGEN_TRY) + rc = smallenough(p->m); /* --- Done --- */