chiark - git - mdw - catacomb/blob - pfilt.h

   1 /* -*-c-*-
   2  *
   3  * $Id: pfilt.h,v 1.4 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Finding and testing prime numbers
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 #ifndef CATACOMB_PFILT_H
  31 #define CATACOMB_PFILT_H
  32
  33 #ifdef __cplusplus
  34   extern "C" {
  35 #endif
  36
  37 /*----- Header files ------------------------------------------------------*/
  38
  39 #ifndef CATACOMB_MP_H
  40 #  include "mp.h"
  41 #endif
  42
  43 #ifndef CATACOMB_PRIMETAB_H
  44 #  include "primetab.h"
  45 #endif
  46
  47 /*----- Data structures ---------------------------------------------------*/
  48
  49 typedef struct pfilt {
  50   mp *m;
  51   smallprime r[NPRIME];
  52 } pfilt;
  53
  54 /*----- Functions provided ------------------------------------------------*/
  55
  56 /* --- @pfilt_smallfactor@ --- *
  57  *
  58  * Arguments:   @mp *m@ = integer to test
  59  *
  60  * Returns:     One of the @PGEN@ result codes.
  61  *
  62  * Use:         Tests a number by dividing by a number of small primes.  This
  63  *              is a useful first step if you're testing random primes; for
  64  *              sequential searches, @pfilt_create@ works better.
  65  */
  66
  67 extern int pfilt_smallfactor(mp */*m*/);
  68
  69 /* --- @pfilt_create@ --- *
  70  *
  71  * Arguments:   @pfilt *p@ = pointer to prime filtering context
  72  *              @mp *m@ = pointer to initial number to test
  73  *
  74  * Returns:     A @PGEN@ result code.
  75  *
  76  * Use:         Tests an initial number for primality by computing its
  77  *              residue modulo various small prime numbers.  This is fairly
  78  *              quick, but not particularly certain.  If a @PGEN_TRY@
  79  *              result is returned, perform Rabin-Miller tests to confirm.
  80  */
  81
  82 extern int pfilt_create(pfilt */*p*/, mp */*m*/);
  83
  84 /* --- @pfilt_destroy@ --- *
  85  *
  86  * Arguments:   @pfilt *p@ = pointer to prime filtering context
  87  *
  88  * Returns:     ---
  89  *
  90  * Use:         Discards a context and all the resources it holds.
  91  */
  92
  93 extern void pfilt_destroy(pfilt */*p*/);
  94
  95 /* --- @pfilt_step@ --- *
  96  *
  97  * Arguments:   @pfilt *p@ = pointer to prime filtering context
  98  *              @mpw step@ = how much to step the number
  99  *
 100  * Returns:     One of the @PGEN@ result codes.
 101  *
 102  * Use:         Steps a number by a small amount.  Stepping is much faster
 103  *              than initializing with a new number.  The test performed is
 104  *              the same simple one used by @primetab_create@, so @PGEN_TRY@
 105  *              results should be followed up by a Rabin-Miller test.
 106  */
 107
 108 extern int pfilt_step(pfilt */*p*/, mpw /*step*/);
 109
 110 /* --- @pfilt_muladd@ --- *
 111  *
 112  * Arguments:   @pfilt *p@ = destination prime filtering context
 113  *              @const pfilt *q@ = source prime filtering context
 114  *              @mpw m@ = number to multiply by
 115  *              @mpw a@ = number to add
 116  *
 117  * Returns:     One of the @PGEN@ result codes.
 118  *
 119  * Use:         Multiplies the number in a prime filtering context by a
 120  *              small value and then adds a small value.  The destination
 121  *              should either be uninitialized or the same as the source.
 122  *
 123  *              Common things to do include multiplying by 2 and adding 0 to
 124  *              turn a prime into a jump for finding other primes with @q@ as
 125  *              a factor of @p - 1@, or multiplying by 2 and adding 1.
 126  */
 127
 128 extern int pfilt_muladd(pfilt */*p*/, const pfilt */*q*/,
 129                         mpw /*m*/, mpw /*a*/);
 130
 131 /* --- @pfilt_jump@ --- *
 132  *
 133  * Arguments:   @pfilt *p@ = pointer to prime filtering context
 134  *              @const pfilt *j@ = pointer to another filtering context
 135  *
 136  * Returns:     One of the @PGEN@ result codes.
 137  *
 138  * Use:         Steps a number by a large amount.  Even so, jumping is much
 139  *              faster than initializing a new number.  The test peformed is
 140  *              the same simple one used by @primetab_create@, so @PGEN_TRY@
 141  *              results should be followed up by a Rabin-Miller test.
 142  *
 143  *              Note that the number stored in the @j@ context is probably
 144  *              better off being even than prime.  The important thing is
 145  *              that all of the residues for the number have already been
 146  *              computed.
 147  */
 148
 149 extern int pfilt_jump(pfilt */*p*/, const pfilt */*j*/);
 150
 151 /*----- That's all, folks -------------------------------------------------*/
 152
 153 #ifdef __cplusplus
 154   }
 155 #endif
 156
 157 #endif