← Back to branch summary

~zulcss/samba/server-dailies-3.4

« back to all changes in this revision

Viewing changes to source4/heimdal/lib/hcrypto/imath/iprime.c

  • Committer: Chuck Short
  • Date: 2010-09-28 20:38:39 UTC
  • Revision ID: zulcss@ubuntu.com-20100928203839-pgjulytsi9ue63x1
Initial version

Show diffs side-by-side

added added

removed removed

Lines of Context:
source4/heimdal/lib/hcrypto/imath/iprime.c
 
1
/*
 
2
  Name:     iprime.c
 
3
  Purpose:  Pseudoprimality testing routines
 
4
  Author:   M. J. Fromberger <http://spinning-yarns.org/michael/>
 
5
  Info:     $Id: iprime.c 635 2008-01-08 18:19:40Z sting $
 
6
 
 
7
  Copyright (C) 2002-2008 Michael J. Fromberger, All Rights Reserved.
 
8
 
 
9
  Permission is hereby granted, free of charge, to any person
 
10
  obtaining a copy of this software and associated documentation files
 
11
  (the "Software"), to deal in the Software without restriction,
 
12
  including without limitation the rights to use, copy, modify, merge,
 
13
  publish, distribute, sublicense, and/or sell copies of the Software,
 
14
  and to permit persons to whom the Software is furnished to do so,
 
15
  subject to the following conditions:
 
16
 
 
17
  The above copyright notice and this permission notice shall be
 
18
  included in all copies or substantial portions of the Software.
 
19
 
 
20
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 
21
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 
22
  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 
23
  NONINFRINGEMENT.  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 
24
  BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 
25
  ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 
26
  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 
27
  SOFTWARE.
 
28
 */
 
29
 
 
30
#include "iprime.h"
 
31
#include <stdlib.h>
 
32
 
 
33
static const int s_ptab[] = {
 
34
    3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
 
35
    47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
 
36
    103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
 
37
    157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
 
38
    211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
 
39
    269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
 
40
    331, 337, 347, 349, 353, 359, 367, 373, 379, 383,
 
41
    389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
 
42
    449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
 
43
    509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
 
44
    587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
 
45
    643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
 
46
    709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
 
47
    773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
 
48
    853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
 
49
    919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
 
50
    991, 997
 
51
#ifdef IMATH_LARGE_PRIME_TABLE
 
52
    , 1009, 1013, 1019, 1021, 1031, 1033,
 
53
    1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091,
 
54
    1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,
 
55
    1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213,
 
56
    1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277,
 
57
    1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307,
 
58
    1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
 
59
    1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,
 
60
    1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493,
 
61
    1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559,
 
62
    1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609,
 
63
    1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
 
64
    1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,
 
65
    1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
 
66
    1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871,
 
67
    1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
 
68
    1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
 
69
    1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,
 
70
    2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111,
 
71
    2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
 
72
    2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243,
 
73
    2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297,
 
74
    2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,
 
75
    2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411,
 
76
    2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
 
77
    2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551,
 
78
    2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633,
 
79
    2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,
 
80
    2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729,
 
81
    2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791,
 
82
    2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851,
 
83
    2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917,
 
84
    2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
 
85
    3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,
 
86
    3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137,
 
87
    3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
 
88
    3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271,
 
89
    3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
 
90
    3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391,
 
91
    3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467,
 
92
    3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533,
 
93
    3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583,
 
94
    3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,
 
95
    3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709,
 
96
    3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779,
 
97
    3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851,
 
98
    3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917,
 
99
    3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
 
100
    4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049,
 
101
    4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111,
 
102
    4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
 
103
    4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243,
 
104
    4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,
 
105
    4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391,
 
106
    4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
 
107
    4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519,
 
108
    4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597,
 
109
    4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657,
 
110
    4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729,
 
111
    4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799,
 
112
    4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889,
 
113
    4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951,
 
114
    4957, 4967, 4969, 4973, 4987, 4993, 4999
 
115
#endif
 
116
};
 
117
static const int s_ptab_size = sizeof(s_ptab)/sizeof(s_ptab[0]);
 
118
 
 
119
/* {{{ mp_int_is_prime(z) */
 
120
 
 
121
/* Test whether z is likely to be prime:
 
122
   MP_TRUE  means it is probably prime
 
123
   MP_FALSE means it is definitely composite
 
124
 */
 
125
mp_result mp_int_is_prime(mp_int z)
 
126
{
 
127
  int       i;
 
128
  mp_small  rem;
 
129
  mp_result res;
 
130
 
 
131
  /* First check for divisibility by small primes; this eliminates a
 
132
     large number of composite candidates quickly
 
133
   */
 
134
  for(i = 0; i < s_ptab_size; ++i) {
 
135
    if((res = mp_int_div_value(z, s_ptab[i], NULL, &rem)) != MP_OK)
 
136
      return res;
 
137
 
 
138
    if(rem == 0)
 
139
      return MP_FALSE;
 
140
  }
 
141
 
 
142
  /* Now try Fermat's test for several prime witnesses (since we now
 
143
     know from the above that z is not a multiple of any of them)
 
144
   */
 
145
  {
 
146
    mpz_t  tmp;
 
147
 
 
148
    if((res = mp_int_init(&tmp)) != MP_OK) return res;
 
149
 
 
150
    for(i = 0; i < 10 && i < s_ptab_size; ++i) {
 
151
      if((res = mp_int_exptmod_bvalue(s_ptab[i], z, z, &tmp)) != MP_OK)
 
152
        return res;
 
153
 
 
154
      if(mp_int_compare_value(&tmp, s_ptab[i]) != 0) {
 
155
        mp_int_clear(&tmp);
 
156
        return MP_FALSE;
 
157
      }
 
158
    }
 
159
 
 
160
    mp_int_clear(&tmp);
 
161
  }
 
162
 
 
163
  return MP_TRUE;
 
164
}
 
165
 
 
166
/* }}} */
 
167
 
 
168
/* {{{ mp_int_find_prime(z) */
 
169
 
 
170
/* Find the first apparent prime in ascending order from z */
 
171
mp_result mp_int_find_prime(mp_int z)
 
172
{
 
173
  mp_result  res;
 
174
 
 
175
  if(mp_int_is_even(z) && ((res = mp_int_add_value(z, 1, z)) != MP_OK))
 
176
    return res;
 
177
 
 
178
  while((res = mp_int_is_prime(z)) == MP_FALSE) {
 
179
    if((res = mp_int_add_value(z, 2, z)) != MP_OK)
 
180
      break;
 
181
 
 
182
  }
 
183
 
 
184
  return res;
 
185
}
 
186
 
 
187
/* }}} */
 
188
 
 
189
/* Here there be dragons */