3 * $Id: pgen.h,v 1.1 1999/11/19 13:17:57 mdw Exp $
5 * Finding and testing prime numbers
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Revision history --------------------------------------------------*
33 * Revision 1.1 1999/11/19 13:17:57 mdw
34 * Prime number generator and tester.
45 /*----- Header files ------------------------------------------------------*/
55 /*----- Constants ---------------------------------------------------------*/
57 #define PGEN_COMPOSITE (-1) /* Number is definitely composite */
58 #define PGEN_MAYBE (0) /* Number may be prime */
59 #define PGEN_PRIME (1) /* Number is definitely prime */
61 /*----- Data structures ---------------------------------------------------*/
65 unsigned char r
[NPRIME
];
68 /*----- Functions provided ------------------------------------------------*/
70 /* --- @pgen_create@ --- *
72 * Arguments: @pgen *p@ = pointer to prime generation context
73 * @mp *m@ = pointer to initial number to test
75 * Returns: One of the @PGEN@ constants above.
77 * Use: Tests an initial number for primality by computing its
78 * residue modulo various small prime numbers. This is fairly
79 * quick, but not particularly certain. If a @PGEN_MAYBE@
80 * result is returned, perform Rabin-Miller tests to confirm.
83 extern int pgen_create(pgen */
*p*/
, mp */
*m*/
);
85 /* --- @pgen_destroy@ --- *
87 * Arguments: @pgen *p@ = pointer to prime generation context
91 * Use: Discards a context and all the resources it holds.
94 extern void pgen_destroy(pgen */
*p*/
);
96 /* --- @pgen_step@ --- *
98 * Arguments: @pgen *p@ = pointer to prime generation context
99 * @mpw step@ = how much to step the number
101 * Returns: One of the @PGEN@ constants above.
103 * Use: Steps a number by a small amount. Stepping is much faster
104 * than initializing with a new number. The test performed is
105 * the same simple one used by @ptab_create@, so @PGEN_MAYBE@
106 * results should be followed up by a Rabin-Miller test.
109 extern int pgen_step(pgen */
*p*/
, mpw
/*step*/);
111 /* --- @pgen_jump@ --- *
113 * Arguments: @pgen *p@ = pointer to prime generation context
114 * @pgen *j@ = pointer to another generation context
116 * Returns: One of the @PGEN@ constants above.
118 * Use: Steps a number by a large amount. Even so, jumping is much
119 * faster than initializing a new number. The test peformed is
120 * the same simple one used by @ptab_create@, so @PGEN_MAYBE@
121 * results should be followed up by a Rabin-Miller test.
123 * Note that the number stored in the @j@ context is probably
124 * better off being even than prime. The important thing is
125 * that all of the residues for the number have already been
129 extern int pgen_jump(pgen */
*p*/
, pgen */
*j*/
);
131 /*----- That's all, folks -------------------------------------------------*/