3 * $Id: pgen-safe.c,v 1.1 1999/12/22 16:01:34 mdw Exp $
5 * Safe prime generation
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 --------------------------------------------------*
32 * $Log: pgen-safe.c,v $
33 * Revision 1.1 1999/12/22 16:01:34 mdw
34 * Find `safe' primes (i.e., %$p = 2q + 1$%).
38 /*----- Header files ------------------------------------------------------*/
44 /*----- Main code ---------------------------------------------------------*/
46 /* --- @pgen_safestep@ --- *
48 * Steps two numbers, %$q$% and %$p = 2q + 1$%, such that neither has any
49 * small factors. %$p$% is put in the event block.
52 int pgen_safestep(int rq
, pgen_event
*ev
, void *p
)
54 pgen_safestepctx
*c
= p
;
55 int prc
= PGEN_ABORT
, qrc
;
59 mp
*p
= mp_split(MP_COPY(ev
->m
));
62 q
= mp_lsr(MP_NEW
, p
, 1);
63 qrc
= pfilt_create(&c
->q
, q
);
64 prc
= pfilt_create(&c
->p
, p
);
70 qrc
= pfilt_step(&c
->q
, 2);
71 prc
= pfilt_step(&c
->p
, 4);
73 if (qrc
== PGEN_FAIL
|| prc
== PGEN_FAIL
)
76 ev
->m
= MP_COPY(c
->p
.m
);
88 /* --- @pgen_safetest@ --- *
90 * Applies Rabin-Miller tests to %$p$% and %$q$%.
93 int pgen_safetest(int rq
, pgen_event
*ev
, void *p
)
95 pgen_safetestctx
*c
= p
;
100 rabin_create(&c
->q
, c
->c
.q
.m
);
101 rabin_create(&c
->p
, c
->c
.p
.m
);
105 mp
*m
= mprand_range(MP_NEW
, c
->c
.q
.m
, ev
->r
, 0);
106 rc
= rabin_test(&c
->p
, m
);
108 rc
= rabin_test(&c
->q
, m
);
112 rabin_destroy(&c
->q
);
113 rabin_destroy(&c
->p
);
119 /*----- That's all, folks -------------------------------------------------*/