monotone

monotone Mtn Source Tree

Root/botan/numthry.h

1/*************************************************
2* Number Theory Header File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#ifndef BOTAN_NUMBTHRY_H__
7#define BOTAN_NUMBTHRY_H__
8
9#include <botan/bigint.h>
10#include <botan/reducer.h>
11
12namespace Botan {
13
14/*************************************************
15* Fused Arithmetic Operations *
16*************************************************/
17BigInt mul_add(const BigInt&, const BigInt&, const BigInt&);
18BigInt sub_mul(const BigInt&, const BigInt&, const BigInt&);
19BigInt mul_mod(const BigInt&, const BigInt&, const BigInt&);
20
21/*************************************************
22* Number Theory Functions *
23*************************************************/
24inline BigInt abs(const BigInt& n) { return n.abs(); }
25
26void divide(const BigInt&, const BigInt&, BigInt&, BigInt&);
27void positive_divide(const BigInt&, const BigInt&, BigInt&, BigInt&);
28void modifying_divide(BigInt&, BigInt&, BigInt&);
29
30BigInt gcd(const BigInt&, const BigInt&);
31BigInt lcm(const BigInt&, const BigInt&);
32
33BigInt square(const BigInt&);
34BigInt inverse_mod(const BigInt&, const BigInt&);
35s32bit jacobi(const BigInt&, const BigInt&);
36BigInt power(const BigInt&, u32bit);
37
38/*************************************************
39* Modular Exponentiation *
40*************************************************/
41BigInt power_mod(const BigInt&, const BigInt&, ModularReducer*);
42BigInt power_mod(const BigInt&, const BigInt&, const BigInt&);
43
44/*************************************************
45* Utility Functions *
46*************************************************/
47u32bit low_zero_bits(const BigInt&);
48
49/*************************************************
50* Primality Testing *
51*************************************************/
52bool check_prime(const BigInt&);
53bool is_prime(const BigInt&);
54bool verify_prime(const BigInt&);
55
56s32bit simple_primality_tests(const BigInt&);
57bool passes_mr_tests(const BigInt&, u32bit = 1);
58bool run_primality_tests(const BigInt&, u32bit = 1);
59
60/*************************************************
61* Random Number Generation *
62*************************************************/
63BigInt random_integer(u32bit, RNG_Quality = SessionKey);
64BigInt random_integer(const BigInt&, const BigInt&, RNG_Quality = SessionKey);
65BigInt random_prime(u32bit, RNG_Quality = SessionKey, const BigInt& = 1,
66 u32bit = 1, u32bit = 2);
67BigInt random_safe_prime(u32bit, RNG_Quality = SessionKey);
68
69SecureVector<byte> generate_dsa_primes(BigInt&, BigInt&, u32bit);
70bool generate_dsa_primes(BigInt&, BigInt&, const byte[], u32bit, u32bit,
71 u32bit = 0);
72
73/*************************************************
74* Prime Numbers *
75*************************************************/
76const u32bit PRIME_TABLE_SIZE = 6541;
77const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256;
78
79extern const u16bit PRIMES[];
80extern const u64bit PRIME_PRODUCTS[];
81
82/*************************************************
83* Miller-Rabin Primality Tester *
84*************************************************/
85class MillerRabin_Test
86 {
87 public:
88 bool passes_test(const BigInt&);
89
90 MillerRabin_Test(const BigInt&);
91 ~MillerRabin_Test() { delete reducer; }
92 private:
93 MillerRabin_Test(const MillerRabin_Test&) {}
94 MillerRabin_Test& operator=(const MillerRabin_Test&) { return (*this); }
95 BigInt n, r, n_minus_1;
96 u32bit s;
97 ModularReducer* reducer;
98 };
99
100}
101
102#endif

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status