1/*
2Copyright (C) 1999-2007 The Botan Project. All rights reserved.
3
4Redistribution and use in source and binary forms, for any use, with or without
5modification, is permitted provided that the following conditions are met:
6
71. Redistributions of source code must retain the above copyright notice, this
8list of conditions, and the following disclaimer.
9
102. Redistributions in binary form must reproduce the above copyright notice,
11this list of conditions, and the following disclaimer in the documentation
12and/or other materials provided with the distribution.
13
14THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED
15WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
16MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ARE DISCLAIMED.
17
18IN NO EVENT SHALL THE AUTHOR(S) OR CONTRIBUTOR(S) BE LIABLE FOR ANY DIRECT,
19INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
20BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
22LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
23OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
24ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25*/
26// LICENSEHEADER_END
27namespace QCA { // WRAPNS_LINE
28/*************************************************
29 * Number Theory Header File *
30 * (C) 1999-2007 The Botan Project *
31 *************************************************/
32
33#ifndef BOTAN_NUMBTHRY_H__
34#define BOTAN_NUMBTHRY_H__
35
36} // WRAPNS_LINE
37#include <botan/bigint.h>
38namespace QCA { // WRAPNS_LINE
39#ifndef BOTAN_MINIMAL_BIGINT
40} // WRAPNS_LINE
41#include <botan/reducer.h>
42namespace QCA { // WRAPNS_LINE
43} // WRAPNS_LINE
44#include <botan/pow_mod.h>
45namespace QCA { // WRAPNS_LINE
46#endif
47
48namespace Botan {
49
50#ifndef BOTAN_MINIMAL_BIGINT
51/*************************************************
52 * Fused Arithmetic Operations *
53 *************************************************/
54BigInt mul_add(const BigInt &, const BigInt &, const BigInt &);
55BigInt sub_mul(const BigInt &, const BigInt &, const BigInt &);
56
57/*************************************************
58 * Number Theory Functions *
59 *************************************************/
60inline BigInt abs(const BigInt &n)
61{
62 return n.abs();
63}
64#endif
65
66void divide(const BigInt &, const BigInt &, BigInt &, BigInt &);
67
68#ifndef BOTAN_MINIMAL_BIGINT
69BigInt gcd(const BigInt &, const BigInt &);
70BigInt lcm(const BigInt &, const BigInt &);
71
72BigInt square(const BigInt &);
73BigInt inverse_mod(const BigInt &, const BigInt &);
74s32bit jacobi(const BigInt &, const BigInt &);
75
76BigInt power_mod(const BigInt &, const BigInt &, const BigInt &);
77
78/*************************************************
79 * Utility Functions *
80 *************************************************/
81u32bit low_zero_bits(const BigInt &);
82
83/*************************************************
84 * Primality Testing *
85 *************************************************/
86bool check_prime(const BigInt &);
87bool is_prime(const BigInt &);
88bool verify_prime(const BigInt &);
89
90s32bit simple_primality_tests(const BigInt &);
91bool passes_mr_tests(const BigInt &, u32bit = 1);
92bool run_primality_tests(const BigInt &, u32bit = 1);
93
94/*************************************************
95 * Random Number Generation *
96 *************************************************/
97BigInt random_integer(u32bit);
98BigInt random_integer(const BigInt &, const BigInt &);
99BigInt random_prime(u32bit, const BigInt & = 1, u32bit = 1, u32bit = 2);
100BigInt random_safe_prime(u32bit);
101
102SecureVector<byte> generate_dsa_primes(BigInt &, BigInt &, u32bit);
103bool generate_dsa_primes(BigInt &, BigInt &, const byte[], u32bit, u32bit, u32bit = 0);
104
105/*************************************************
106 * Prime Numbers *
107 *************************************************/
108const u32bit PRIME_TABLE_SIZE = 6541;
109const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256;
110
111extern const u16bit PRIMES[];
112extern const u64bit PRIME_PRODUCTS[];
113
114/*************************************************
115 * Miller-Rabin Primality Tester *
116 *************************************************/
117class MillerRabin_Test
118{
119public:
120 bool passes_test(const BigInt &);
121 MillerRabin_Test(const BigInt &);
122
123private:
124 BigInt n, r, n_minus_1;
125 u32bit s;
126 Fixed_Exponent_Power_Mod pow_mod;
127 Modular_Reducer reducer;
128};
129#endif
130
131}
132
133#endif
134} // WRAPNS_LINE
135

source code of qca/src/botantools/botan/botan/numthry.h