3 * $Id: pgen.c,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.
38 /*----- Header files ------------------------------------------------------*/
46 /*----- Main code ---------------------------------------------------------*/
48 /* --- @pgen_create@ --- *
50 * Arguments: @pgen *p@ = pointer to prime generation context
51 * @mp *m@ = pointer to initial number to test
53 * Returns: One of the @PGEN@ constants above.
55 * Use: Tests an initial number for primality by computing its
56 * residue modulo various small prime numbers. This is fairly
57 * quick, but not particularly certain. If a @PGEN_MAYBE@
58 * result is returned, perform Rabin-Miller tests to confirm.
61 int pgen_create(pgen
*p
, mp
*m
)
69 /* --- Take a copy of the number --- */
74 /* --- Fill in the residues --- */
76 mp_build(&q
, &qw
, &qw
+ 1);
77 for (i
= 0; i
< NPRIME
; i
++) {
81 if (!p
->r
[i
] && rc
== PGEN_MAYBE
) {
82 if (MP_LEN(m
) == 1 && m
->v
[0] == ptab
[i
])
95 /* --- @pgen_destroy@ --- *
97 * Arguments: @pgen *p@ = pointer to prime generation context
101 * Use: Discards a context and all the resources it holds.
104 void pgen_destroy(pgen
*p
)
109 /* --- @pgen_step@ --- *
111 * Arguments: @pgen *p@ = pointer to prime generation context
112 * @mpw step@ = how much to step the number
114 * Returns: One of the @PGEN@ constants above.
116 * Use: Steps a number by a small amount. Stepping is much faster
117 * than initializing with a new number. The test performed is
118 * the same simple one used by @ptab_create@, so @PGEN_MAYBE@
119 * results should be followed up by a Rabin-Miller test.
122 int pgen_step(pgen
*p
, mpw step
)
128 /* --- Add the step on to the number --- */
130 mp_build(&s
, &step
, &step
+ 1);
131 p
->m
= mp_add(p
->m
, p
->m
, &s
);
133 /* --- Update the residue table --- */
135 for (i
= 0; i
< NPRIME
; i
++) {
136 p
->r
[i
] = (p
->r
[i
] + step
) % ptab
[i
];
137 if (!p
->r
[i
] && rc
== PGEN_MAYBE
) {
138 if (MP_LEN(p
->m
) == 1 && p
->m
->v
[0] == ptab
[i
])
150 /* --- @pgen_jump@ --- *
152 * Arguments: @pgen *p@ = pointer to prime generation context
153 * @pgen *j@ = pointer to another generation context
155 * Returns: One of the @PGEN@ constants above.
157 * Use: Steps a number by a large amount. Even so, jumping is much
158 * faster than initializing a new number. The test peformed is
159 * the same simple one used by @ptab_create@, so @PGEN_MAYBE@
160 * results should be followed up by a Rabin-Miller test.
162 * Note that the number stored in the @j@ context is probably
163 * better off being even than prime. The important thing is
164 * that all of the residues for the number have already been
168 int pgen_jump(pgen
*p
, pgen
*j
)
173 /* --- Add the step on --- */
175 p
->m
= mp_add(p
->m
, p
->m
, j
->m
);
177 /* --- Update the residue table --- */
179 for (i
= 0; i
< NPRIME
; i
++) {
180 p
->r
[i
] = p
->r
[i
] + j
->r
[i
];
181 if (p
->r
[i
] > ptab
[i
])
183 if (!p
->r
[i
] && rc
== PGEN_MAYBE
) {
184 if (MP_LEN(p
->m
) == 1 && p
->m
->v
[0] == ptab
[i
])
196 /*----- Test code ---------------------------------------------------------*/
200 #include <mLib/testrig.h>
202 static int verify(dstr
*v
)
204 mp
*m
= *(mp
**)v
[0].buf
;
205 mp
*r
= *(mp
**)v
[1].buf
;
210 static char baton
[] = "/-\\|";
214 mp_build(&g
, &gw
, &gw
+ 1);
215 rc
= pgen_create(&p
, m
);
217 if (rc
== PGEN_PRIME
)
219 if (rc
== PGEN_MAYBE
) {
222 rabin_create(&r
, p
.m
);
223 for (i
= 0; i
< 5; i
++) {
225 if (rabin_test(&r
, &g
) == PGEN_COMPOSITE
)
236 rc
= pgen_step(&p
, 2);
239 if (MP_CMP(p
.m
, !=, r
)) {
240 fputs("\n*** failed.", stderr
);
241 fputs("\nm = ", stderr
); mp_writefile(m
, stderr
, 10);
242 fputs("\np = ", stderr
); mp_writefile(p
.m
, stderr
, 10);
243 fputs("\nr = ", stderr
); mp_writefile(r
, stderr
, 10);
254 static test_chunk tests
[] = {
255 { "pgen", verify
, { &type_mp
, &type_mp
, 0 } },
259 int main(int argc
, char *argv
[])
262 test_run(argc
, argv
, tests
, SRCDIR
"/tests/pgen");
268 /*----- That's all, folks -------------------------------------------------*/