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
142
143
144
145
146
|
/*
* Number Theory Functions
* (C) 1999-2007 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
#ifndef BOTAN_NUMBER_THEORY_H__
#define BOTAN_NUMBER_THEORY_H__
#include <botan/bigint.h>
#include <botan/pow_mod.h>
#include <botan/rng.h>
namespace Botan {
/**
* Fused Arithmetic Operation
*/
BigInt BOTAN_DLL mul_add(const BigInt&, const BigInt&, const BigInt&);
BigInt BOTAN_DLL sub_mul(const BigInt&, const BigInt&, const BigInt&);
/*
* Number Theory Functions
*/
inline BigInt abs(const BigInt& n) { return n.abs(); }
/**
* Compute the greatest common divisor
* @param x a positive integer
* @param y a positive integer
* @return gcd(x,y)
*/
BigInt BOTAN_DLL gcd(const BigInt& x, const BigInt& y);
/**
* Least common multiple
* @param x a positive integer
* @param y a positive integer
* @return z, smallest integer such that z % x == 0 and z % y == 0
*/
BigInt BOTAN_DLL lcm(const BigInt& x, const BigInt& y);
/**
* @param x an integer
* @return (x*x)
*/
BigInt BOTAN_DLL square(const BigInt& x);
/**
* Modular inversion
* @param x a positive integer
* @param modulus a positive integer
* @return y st (x*y) % modulus == 1
*/
BigInt BOTAN_DLL inverse_mod(const BigInt& x,
const BigInt& modulus);
/**
* Compute the Jacobi symbol. If n is prime, this is equivalent
* to the Legendre symbol.
* @see http://mathworld.wolfram.com/JacobiSymbol.html
*
* @param a is a non-negative integer
* @param n is an odd integer > 1
* @return (n / m)
*/
s32bit BOTAN_DLL jacobi(const BigInt& a,
const BigInt& n);
/**
* Modular exponentation
*/
BigInt BOTAN_DLL power_mod(const BigInt&, const BigInt&, const BigInt&);
/**
* Compute the square root of x modulo a prime using the
* Shanks-Tonnelli algorithm
*
* @param x the input
* @param p the prime
* @return y such that (y*y)%p == x, or -1 if no such integer
*/
BigInt BOTAN_DLL ressol(const BigInt& x, const BigInt& p);
/**
* @param x an integer
* @return count of the zero bits in x, or, equivalently, the largest
* value of n such that 2^n divides x evently
*/
u32bit BOTAN_DLL low_zero_bits(const BigInt& x);
/*
* Primality Testing
*/
bool BOTAN_DLL primality_test(const BigInt& n,
RandomNumberGenerator& rng,
u32bit level = 1);
inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
{ return primality_test(n, rng, 0); }
inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
{ return primality_test(n, rng, 1); }
inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
{ return primality_test(n, rng, 2); }
/*
* Random Number Generation
*/
BigInt BOTAN_DLL random_prime(RandomNumberGenerator& rng,
u32bit bits, const BigInt& coprime = 1,
u32bit equiv = 1, u32bit equiv_mod = 2);
BigInt BOTAN_DLL random_safe_prime(RandomNumberGenerator& rng,
u32bit bits);
/*
* DSA Parameter Generation
*/
class Algorithm_Factory;
SecureVector<byte> BOTAN_DLL
generate_dsa_primes(RandomNumberGenerator& rng,
Algorithm_Factory& af,
BigInt& p, BigInt& q,
u32bit pbits, u32bit qbits);
bool BOTAN_DLL
generate_dsa_primes(RandomNumberGenerator& rng,
Algorithm_Factory& af,
BigInt& p_out, BigInt& q_out,
u32bit p_bits, u32bit q_bits,
const MemoryRegion<byte>& seed);
/*
* Prime Numbers
*/
const u32bit PRIME_TABLE_SIZE = 6541;
extern const u16bit BOTAN_DLL PRIMES[];
}
#endif
|
