Mercurial > dropbear

comparison tomsfastmath/src/numtheory/fp_prime_random_ex.c @ 643:a362b62d38b2 dropbear-tfm

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add tomsfastmath from git rev bfa4582842bc3bab42e4be4aed5703437049502a with Makefile.in renamed
author Matt Johnston <matt@ucc.asn.au>
date Wed, 23 Nov 2011 18:10:20 +0700
parents
children
comparison
equal deleted inserted replaced
642:33fd2f3499d2 643:a362b62d38b2
1 /* TomsFastMath, a fast ISO C bignum library.
2 *
3 * This project is meant to fill in where LibTomMath
4 * falls short. That is speed ;-)
5 *
6 * This project is public domain and free for all purposes.
7 *
8 * Tom St Denis, [email protected]
9 */
10 #include <tfm.h>
11
12 /* This is possibly the mother of all prime generation functions, muahahahahaha! */
13 int fp_prime_random_ex(fp_int *a, int t, int size, int flags, tfm_prime_callback cb, void *dat)
14 {
15 unsigned char *tmp, maskAND, maskOR_msb, maskOR_lsb;
16 int res, err, bsize, maskOR_msb_offset;
17
18 /* sanity check the input */
19 if (size <= 1 || t <= 0) {
20 return FP_VAL;
21 }
22
23 /* TFM_PRIME_SAFE implies TFM_PRIME_BBS */
24 if (flags & TFM_PRIME_SAFE) {
25 flags |= TFM_PRIME_BBS;
26 }
27
28 /* calc the byte size */
29 bsize = (size>>3)+(size&7?1:0);
30
31 /* we need a buffer of bsize bytes */
32 tmp = malloc(bsize);
33 if (tmp == NULL) {
34 return FP_MEM;
35 }
36
37 /* calc the maskAND value for the MSbyte*/
38 maskAND = 0xFF >> (8 - (size & 7));
39
40 /* calc the maskOR_msb */
41 maskOR_msb = 0;
42 maskOR_msb_offset = (size - 2) >> 3;
43 if (flags & TFM_PRIME_2MSB_ON) {
44 maskOR_msb |= 1 << ((size - 2) & 7);
45 } else if (flags & TFM_PRIME_2MSB_OFF) {
46 maskAND &= ~(1 << ((size - 2) & 7));
47 }
48
49 /* get the maskOR_lsb */
50 maskOR_lsb = 1;
51 if (flags & TFM_PRIME_BBS) {
52 maskOR_lsb |= 3;
53 }
54
55 do {
56 /* read the bytes */
57 if (cb(tmp, bsize, dat) != bsize) {
58 err = FP_VAL;
59 goto error;
60 }
61
62 /* work over the MSbyte */
63 tmp[0] &= maskAND;
64 tmp[0] |= 1 << ((size - 1) & 7);
65
66 /* mix in the maskORs */
67 tmp[maskOR_msb_offset] |= maskOR_msb;
68 tmp[bsize-1] |= maskOR_lsb;
69
70 /* read it in */
71 fp_read_unsigned_bin(a, tmp, bsize);
72
73 /* is it prime? */
74 res = fp_isprime(a);
75 if (res == FP_NO) continue;
76
77 if (flags & TFM_PRIME_SAFE) {
78 /* see if (a-1)/2 is prime */
79 fp_sub_d(a, 1, a);
80 fp_div_2(a, a);
81
82 /* is it prime? */
83 res = fp_isprime(a);
84 }
85 } while (res == FP_NO);
86
87 if (flags & TFM_PRIME_SAFE) {
88 /* restore a to the original value */
89 fp_mul_2(a, a);
90 fp_add_d(a, 1, a);
91 }
92
93 err = FP_OKAY;
94 error:
95 free(tmp);
96 return err;
97 }
98
99 /* $Source$ */
100 /* $Revision$ */
101 /* $Date$ */