chiark - git - mdw - catacomb/blob - pub/keycheck-mp.c

   1 /* -*-c-*-
   2  *
   3  * Key consistency checking tools for large integers
   4  *
   5  * (c) 2001 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <mLib/dstr.h>
  31
  32 #include "fibrand.h"
  33 #include "grand.h"
  34 #include "keycheck.h"
  35 #include "mp.h"
  36 #include "mprand.h"
  37 #include "pfilt.h"
  38 #include "pgen.h"
  39 #include "rabin.h"
  40 #include "rand.h"
  41
  42 /*----- Main code ---------------------------------------------------------*/
  43
  44 /* --- @keycheck_prime@ --- *
  45  *
  46  * Arguments:   @keycheck *kc@ = keycheck state
  47  *              @unsigned sev@ = severity if not prime
  48  *              @mp *m@ = a number to check for primality
  49  *              @const char *name@ = name of this number
  50  *
  51  * Returns:     Zero if OK, or return status from function.
  52  *
  53  * Use:         Checks that a number is prime.
  54  */
  55
  56 int keycheck_prime(keycheck *kc, unsigned sev, mp *m, const char *name)
  57 {
  58   int rc;
  59
  60   rc = pfilt_smallfactor(m);
  61   if (rc == PGEN_TRY) {
  62     rabin rn;
  63     grand *r = fibrand_create(0);
  64     unsigned n;
  65     mp *x = MP_NEW;
  66
  67     r->ops->misc(r, GRAND_SEEDRAND, &rand_global);
  68     n = rabin_iters(mp_bits(m));
  69     rabin_create(&rn, m);
  70     do {
  71       x = mprand_range(x, m, r, 0);
  72       rc = rabin_test(&rn, x);
  73       n--;
  74     } while (n && rc == PGEN_PASS);
  75     rabin_destroy(&rn);
  76     mp_drop(x);
  77     r->ops->destroy(r);
  78   }
  79   if (rc != PGEN_FAIL)
  80     rc = 0;
  81   else
  82     rc = keycheck_report(kc, sev, "%s not prime", name);
  83   return (rc);
  84 }
  85
  86 /*----- That's all, folks -------------------------------------------------*/