1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
/*
* Copyright (c) mjh-EDV Beratung, 1996-1999
* mjh-EDV Beratung - 63263 Neu-Isenburg - Rosenstrasse 12
* Tel +49 6102 328279 - Fax +49 6102 328278
* Email info@mjh.teddy-net.com
*
* Author: Jordan Hrycaj <jordan@mjh.teddy-net.com>
*
* $Id: make-primes.h,v 1.1 2000/08/14 20:51:36 jordan Exp $
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the Free
* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifndef __MAKE_PRIME_H__
#define __MAKE_PRIME_H__
#include "gmp.h"
/* call back functions available to print keep-alive periods and
symbols while the algoriths are running. */
extern void xprint2 (const char *text); /* print on stderr */
extern void xprint1 (const char *text); /* print on stdout */
/* --------------------------------------------------------------------
Genererate a random numer with at most (size+7)/8 bits. If the last
argument MOD is non-NULL, the resulting randum number is chosen with
gcd (num, MOD) == 1.
----------------------------------------------------------------- */
extern void get_random_num (mpz_t *num, unsigned size, mpz_t *MOD);
/* --------------------------------------------------------------------
Test, whether the number num is a prime with the probability weight
prob_weight denoting the maximal number of rounds in the Miller Rabin
test. Roughly spoken, this test fails to detect a compsite number
with probability 1/4 in each round. So the probability of accepting
a prime although it is composite is about 2^(-2*prob_weight).
If the test returns 0, the argument num is definitely not a prime.
As an example, if prob_weight is 10, with probablilty 10^-6, the
test fails when it claims the argument value is a prime. If the
argument prob_weight is 20, the test results in a wrong yes answer
with probablilty 10^-12.
----------------------------------------------------------------- */
extern unsigned number_is_a_prime (mpz_t *num, unsigned prob_weight) ;
/* --------------------------------------------------------------------
Find a prime by testing at most max_tries odd random numbers. These
randum numbers are sized of min_bits bits. The test, whether the
random number is prime, or not fails with probability
2^(-2*prob_weight).
The function returns the argument max_tries+1 minus the number of
tests, left. Upon failure, 0 is returned.
----------------------------------------------------------------- */
extern unsigned /* number of rounds before fail */
get_random_prime
(mpz_t *prime, /* set as result, if positive return value */
unsigned min_bits, /* aproximate size of the prime */
unsigned prob_weight, /* probabiltiy weight for Miller Rabin test */
unsigned max_tries, /* try this many random nums */
void (*prt) (const char*)); /* prints keep alive messages, unless NULL */
/* --------------------------------------------------------------------
Find a prime module P = Q * t + 1 for some (small) number t, and a
generator G for P. The values for P, G and Q will G will be set by
the function. Upon success, the genrator G is also the
function return value, and 0 otherwise.
----------------------------------------------------------------- */
extern unsigned /* the generator G to be found, or 0 */
get_generated_prime_module
(mpz_t *P, /* the prime module to be found */
unsigned *G, /* the generator (mod p) to be found */
mpz_t *Q, /* input: a large prime to start, with */
unsigned min_bits, /* aproximate size of the prime */
void (*prt)(const char*)) ; /* prints keep alive messages, unless NULL */
/* --------------------------------------------------------------------
customizing parameters for the probabilistic algorithms
----------------------------------------------------------------- */
#ifdef __MAKE_PRIME_INTERNAL__
/* the hash function is used to derive new test numbers from a
given random value */
#define MAKE_PRIME_HASH_TYPE "ripemd160"
/* try this often to generate a prime mdule and a primitive
element for this module */
#define TRY_GENERATE_PRIME_MODULE 10
/* try this many times a new random number whether it satisfies
the prime condition */
#define TRY_RANDOM_IS_PRIME 800
/* given a prime, try this many times to derive another prime and
a generator for the corresponding multiplicative group */
#define TRY_PRIME_HAS_GENERATOR 1200
/* probability of a false prime is 2^(-2*PRIME_PROBABBILTY_WEIGHT) */
#define PRIME_PROBABBILTY_WEIGHT 20
/* some fancy test is printed in get_generated_prime_module ()
unless the argument prt is NULL */
#define GENERATING_PRIMES_TXT "Generating primes: "
#define ADVANCING_NEXT_TXT "Retrying: "
#define NOMORE_NEXT_TXT "Stop."
#endif
/* Posix threads initialization support */
#ifdef USE_PTHREADS
void prime_maker_sema_create (void *attr);
void prime_maker_sema_destroy (void);
#endif
#endif /* __MAKE_PRIME_H__ */
|
