Botan 3.9.0
Crypto and TLS for C&
primality.cpp
Go to the documentation of this file.
1/*
2* (C) 2016,2018 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/primality.h>
8
9#include <botan/bigint.h>
10#include <botan/numthry.h>
11#include <botan/rng.h>
12#include <botan/internal/barrett.h>
13#include <botan/internal/monty.h>
14#include <botan/internal/monty_exp.h>
15
16namespace Botan {
17
18bool is_lucas_probable_prime(const BigInt& C, const Barrett_Reduction& mod_C) {
19 BOTAN_ARG_CHECK(C.is_positive(), "Argument should be a positive integer");
20
21 if(C == 2 || C == 3 || C == 5 || C == 7 || C == 11 || C == 13) {
22 return true;
23 }
24
25 if(C <= 1 || C.is_even()) {
26 return false;
27 }
28
30
31 for(;;) {
32 int32_t j = jacobi(D, C);
33 if(j == 0) {
34 return false;
35 }
36
37 if(j == -1) {
38 break;
39 }
40
41 // Check 5, -7, 9, -11, 13, -15, 17, ...
42 if(D.is_negative()) {
43 D.flip_sign();
44 D += 2;
45 } else {
46 D += 2;
47 D.flip_sign();
48 }
49
50 if(D == 17 && is_perfect_square(C).is_nonzero()) {
51 return false;
52 }
53 }
54
55 if(D.is_negative()) {
56 D += C;
57 }
58
59 const BigInt K = C + 1;
60 const size_t K_bits = K.bits() - 1;
61
62 BigInt U = BigInt::one();
63 BigInt V = BigInt::one();
64
65 BigInt Ut;
66 BigInt Vt;
67 BigInt U2;
68 BigInt V2;
69
70 for(size_t i = 0; i != K_bits; ++i) {
71 const bool k_bit = K.get_bit(K_bits - 1 - i);
72
73 Ut = mod_C.multiply(U, V);
74
75 Vt = mod_C.reduce(mod_C.square(V) + mod_C.multiply(D, mod_C.square(U)));
76 Vt.ct_cond_add(Vt.is_odd(), C);
77 Vt >>= 1;
78 Vt = mod_C.reduce(Vt);
79
80 U = Ut;
81 V = Vt;
82
83 U2 = mod_C.reduce(Ut + Vt);
84 U2.ct_cond_add(U2.is_odd(), C);
85 U2 >>= 1;
86
87 V2 = mod_C.reduce(Vt + mod_C.multiply(Ut, D));
88 V2.ct_cond_add(V2.is_odd(), C);
89 V2 >>= 1;
90
91 U.ct_cond_assign(k_bit, U2);
92 V.ct_cond_assign(k_bit, V2);
93 }
94
95 return (U == 0);
96}
97
99 if(n == 2) {
100 return true;
101 } else if(n <= 1 || n.is_even()) {
102 return false;
103 }
104
105 Montgomery_Params monty_n(n, mod_n);
106 const auto base = BigInt::from_word(2);
107 return passes_miller_rabin_test(n, mod_n, monty_n, base) && is_lucas_probable_prime(n, mod_n);
108}
109
111 const Barrett_Reduction& mod_n,
112 const Montgomery_Params& monty_n,
113 const BigInt& a) {
114 if(n < 3 || n.is_even()) {
115 return false;
116 }
117
118 BOTAN_ASSERT_NOMSG(n > 1);
119
120 const BigInt n_minus_1 = n - 1;
121 const size_t s = low_zero_bits(n_minus_1);
122 const BigInt nm1_s = n_minus_1 >> s;
123 const size_t n_bits = n.bits();
124
125 const size_t powm_window = 4;
126
127 auto powm_a_n = monty_precompute(monty_n, a, powm_window);
128
129 BigInt y = monty_execute(*powm_a_n, nm1_s, n_bits).value();
130
131 if(y == 1 || y == n_minus_1) {
132 return true;
133 }
134
135 for(size_t i = 1; i != s; ++i) {
136 y = mod_n.square(y);
137
138 if(y == 1) { // found a non-trivial square root
139 return false;
140 }
141
142 /*
143 -1 is the trivial square root of unity, so ``a`` is not a
144 witness for this number - give up
145 */
146 if(y == n_minus_1) {
147 return true;
148 }
149 }
150
151 return false;
152}
153
155 const Barrett_Reduction& mod_n,
157 size_t test_iterations) {
158 if(n < 3 || n.is_even()) {
159 return false;
160 }
161
162 Montgomery_Params monty_n(n, mod_n);
163
164 for(size_t i = 0; i != test_iterations; ++i) {
165 const BigInt a = BigInt::random_integer(rng, BigInt::from_word(2), n);
166
167 if(!passes_miller_rabin_test(n, mod_n, monty_n, a)) {
168 return false;
169 }
170 }
171
172 // Failed to find a counterexample
173 return true;
174}
175
176size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random) {
177 const size_t base = (prob + 2) / 2; // worst case 4^-t error rate
178
179 /*
180 * If the candidate prime was maliciously constructed, we can't rely
181 * on arguments based on p being random.
182 */
183 if(!random) {
184 return base;
185 }
186
187 /*
188 * For randomly chosen numbers we can use the estimates from
189 * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf
190 *
191 * These values are derived from the inequality for p(k,t) given on
192 * the second page.
193 */
194 if(prob <= 128) {
195 if(n_bits >= 1536) {
196 return 4; // < 2^-133
197 }
198 if(n_bits >= 1024) {
199 return 6; // < 2^-133
200 }
201 if(n_bits >= 512) {
202 return 12; // < 2^-129
203 }
204 if(n_bits >= 256) {
205 return 29; // < 2^-128
206 }
207 }
208
209 /*
210 If the user desires a smaller error probability than we have
211 precomputed error estimates for, just fall back to using the worst
212 case error rate.
213 */
214 return base;
215}
216
217} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
BigInt reduce(const BigInt &x) const
Definition barrett.cpp:194
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition barrett.cpp:162
BigInt square(const BigInt &x) const
Definition barrett.cpp:183
void ct_cond_add(bool predicate, const BigInt &value)
Definition bigint.cpp:453
bool is_odd() const
Definition bigint.h:445
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:43
void ct_cond_assign(bool predicate, const BigInt &other)
Definition bigint.cpp:531
void flip_sign()
Definition bigint.h:586
static BigInt one()
Definition bigint.h:54
size_t bits() const
Definition bigint.cpp:311
bool is_even() const
Definition bigint.h:439
static BigInt from_word(word n)
Definition bigint.cpp:34
bool is_negative() const
Definition bigint.h:559
bool is_positive() const
Definition bigint.h:565
bool get_bit(size_t n) const
Definition bigint.h:496
BigInt value() const
Definition monty.cpp:245
bool is_lucas_probable_prime(const BigInt &C, const Barrett_Reduction &mod_C)
Definition primality.cpp:18
size_t low_zero_bits(const BigInt &n)
Definition numthry.cpp:167
bool is_bailie_psw_probable_prime(const BigInt &n, const Barrett_Reduction &mod_n)
Definition primality.cpp:98
bool passes_miller_rabin_test(const BigInt &n, const Barrett_Reduction &mod_n, const Montgomery_Params &monty_n, const BigInt &a)
Montgomery_Int monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
BigInt is_perfect_square(const BigInt &C)
Definition numthry.cpp:320
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits, bool const_time)
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition numthry.cpp:116
bool is_miller_rabin_probable_prime(const BigInt &n, const Barrett_Reduction &mod_n, RandomNumberGenerator &rng, size_t test_iterations)