aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/math/gfpmath/curve_gfp.h1
-rw-r--r--src/math/gfpmath/point_gfp.cpp4
-rw-r--r--src/math/numbertheory/numthry.cpp100
-rw-r--r--src/math/numbertheory/numthry.h16
-rw-r--r--src/math/numbertheory/reducer.cpp19
-rw-r--r--src/math/numbertheory/reducer.h28
6 files changed, 84 insertions, 84 deletions
diff --git a/src/math/gfpmath/curve_gfp.h b/src/math/gfpmath/curve_gfp.h
index 6010183b8..697065dfe 100644
--- a/src/math/gfpmath/curve_gfp.h
+++ b/src/math/gfpmath/curve_gfp.h
@@ -11,6 +11,7 @@
#define BOTAN_GFP_CURVE_H__
#include <botan/numthry.h>
+#include <botan/reducer.h>
namespace Botan {
diff --git a/src/math/gfpmath/point_gfp.cpp b/src/math/gfpmath/point_gfp.cpp
index c28b1eb62..06c42d18c 100644
--- a/src/math/gfpmath/point_gfp.cpp
+++ b/src/math/gfpmath/point_gfp.cpp
@@ -229,7 +229,7 @@ BigInt PointGFp::get_affine_y() const
const Modular_Reducer& mod_p = curve.mod_p();
- BigInt z3 = mod_p.multiply(coord_z, mod_p.square(coord_z));
+ BigInt z3 = mod_p.cube(coord_z);
return mod_p.multiply(coord_y, inverse_mod(z3, curve.get_p()));
}
@@ -254,7 +254,7 @@ void PointGFp::check_invariants() const
const Modular_Reducer& mod_p = curve.mod_p();
BigInt y2 = mod_p.square(coord_y);
- BigInt x3 = mod_p.multiply(coord_x, mod_p.square(coord_x));
+ BigInt x3 = mod_p.cube(coord_x);
BigInt ax = mod_p.multiply(coord_x, curve.get_a());
diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp
index 0740ea21b..e4c52323e 100644
--- a/src/math/numbertheory/numthry.cpp
+++ b/src/math/numbertheory/numthry.cpp
@@ -1,11 +1,12 @@
/*
* Number Theory Functions
-* (C) 1999-2009 Jack Lloyd
+* (C) 1999-2010 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
#include <botan/numthry.h>
+#include <botan/reducer.h>
#include <botan/internal/bit_ops.h>
#include <algorithm>
@@ -14,6 +15,62 @@ namespace Botan {
namespace {
/*
+* Miller-Rabin Primality Tester
+*/
+class MillerRabin_Test
+ {
+ public:
+ bool passes_test(const BigInt& nonce);
+ MillerRabin_Test(const BigInt& num);
+ private:
+ BigInt n, r, n_minus_1;
+ u32bit s;
+ Fixed_Exponent_Power_Mod pow_mod;
+ Modular_Reducer reducer;
+ };
+
+/*
+* Miller-Rabin Test
+*/
+bool MillerRabin_Test::passes_test(const BigInt& a)
+ {
+ if(a < 2 || a >= n_minus_1)
+ throw Invalid_Argument("Bad size for nonce in Miller-Rabin test");
+
+ BigInt y = pow_mod(a);
+ if(y == 1 || y == n_minus_1)
+ return true;
+
+ for(u32bit i = 1; i != s; ++i)
+ {
+ y = reducer.square(y);
+
+ if(y == 1)
+ return false;
+ if(y == n_minus_1)
+ return true;
+ }
+ return false;
+ }
+
+/*
+* Miller-Rabin Constructor
+*/
+MillerRabin_Test::MillerRabin_Test(const BigInt& num)
+ {
+ if(num.is_even() || num < 3)
+ throw Invalid_Argument("MillerRabin_Test: Invalid number for testing");
+
+ n = num;
+ n_minus_1 = n - 1;
+ s = low_zero_bits(n_minus_1);
+ r = n_minus_1 >> s;
+
+ pow_mod = Fixed_Exponent_Power_Mod(r, n);
+ reducer = Modular_Reducer(n);
+ }
+
+/*
* Miller-Rabin Iterations
*/
u32bit miller_rabin_test_iterations(u32bit bits, bool verify)
@@ -300,45 +357,4 @@ bool passes_mr_tests(RandomNumberGenerator& rng,
return true;
}
-/*
-* Miller-Rabin Test
-*/
-bool MillerRabin_Test::passes_test(const BigInt& a)
- {
- if(a < 2 || a >= n_minus_1)
- throw Invalid_Argument("Bad size for nonce in Miller-Rabin test");
-
- BigInt y = pow_mod(a);
- if(y == 1 || y == n_minus_1)
- return true;
-
- for(u32bit i = 1; i != s; ++i)
- {
- y = reducer.square(y);
-
- if(y == 1)
- return false;
- if(y == n_minus_1)
- return true;
- }
- return false;
- }
-
-/*
-* Miller-Rabin Constructor
-*/
-MillerRabin_Test::MillerRabin_Test(const BigInt& num)
- {
- if(num.is_even() || num < 3)
- throw Invalid_Argument("MillerRabin_Test: Invalid number for testing");
-
- n = num;
- n_minus_1 = n - 1;
- s = low_zero_bits(n_minus_1);
- r = n_minus_1 >> s;
-
- pow_mod = Fixed_Exponent_Power_Mod(r, n);
- reducer = Modular_Reducer(n);
- }
-
}
diff --git a/src/math/numbertheory/numthry.h b/src/math/numbertheory/numthry.h
index ae2c219fc..080f184a4 100644
--- a/src/math/numbertheory/numthry.h
+++ b/src/math/numbertheory/numthry.h
@@ -9,7 +9,6 @@
#define BOTAN_NUMBER_THEORY_H__
#include <botan/bigint.h>
-#include <botan/reducer.h>
#include <botan/pow_mod.h>
#include <botan/rng.h>
@@ -100,21 +99,6 @@ const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256;
extern const u16bit BOTAN_DLL PRIMES[];
extern const u64bit PRIME_PRODUCTS[];
-/*
-* Miller-Rabin Primality Tester
-*/
-class BOTAN_DLL MillerRabin_Test
- {
- public:
- bool passes_test(const BigInt&);
- MillerRabin_Test(const BigInt&);
- private:
- BigInt n, r, n_minus_1;
- u32bit s;
- Fixed_Exponent_Power_Mod pow_mod;
- Modular_Reducer reducer;
- };
-
}
#endif
diff --git a/src/math/numbertheory/reducer.cpp b/src/math/numbertheory/reducer.cpp
index aa53f1a0e..257ece56e 100644
--- a/src/math/numbertheory/reducer.cpp
+++ b/src/math/numbertheory/reducer.cpp
@@ -1,12 +1,11 @@
/*
* Modular Reducer
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2010 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
#include <botan/reducer.h>
-#include <botan/numthry.h>
#include <botan/internal/mp_core.h>
namespace Botan {
@@ -78,20 +77,4 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const
return t1;
}
-/*
-* Multiply, followed by a reduction
-*/
-BigInt Modular_Reducer::multiply(const BigInt& x, const BigInt& y) const
- {
- return reduce(x * y);
- }
-
-/*
-* Square, followed by a reduction
-*/
-BigInt Modular_Reducer::square(const BigInt& x) const
- {
- return reduce(Botan::square(x));
- }
-
}
diff --git a/src/math/numbertheory/reducer.h b/src/math/numbertheory/reducer.h
index baaab47a4..80c0f27e1 100644
--- a/src/math/numbertheory/reducer.h
+++ b/src/math/numbertheory/reducer.h
@@ -1,14 +1,14 @@
/*
* Modular Reducer
-* (C) 1999-2007 Jack Lloyd
+* (C) 1999-2010 Jack Lloyd
*
* Distributed under the terms of the Botan license
*/
-#ifndef BOTAN_MODARITH_H__
-#define BOTAN_MODARITH_H__
+#ifndef BOTAN_MODULAR_REDUCER_H__
+#define BOTAN_MODULAR_REDUCER_H__
-#include <botan/bigint.h>
+#include <botan/numthry.h>
namespace Botan {
@@ -18,10 +18,26 @@ namespace Botan {
class BOTAN_DLL Modular_Reducer
{
public:
- BigInt multiply(const BigInt& x, const BigInt& y) const;
- BigInt square(const BigInt& x) const;
BigInt reduce(const BigInt& x) const;
+ /**
+ * Multiply mod p
+ */
+ BigInt multiply(const BigInt& x, const BigInt& y) const
+ { return reduce(x * y); }
+
+ /**
+ * Square mod p
+ */
+ BigInt square(const BigInt& x) const
+ { return reduce(Botan::square(x)); }
+
+ /**
+ * Cube mod p
+ */
+ BigInt cube(const BigInt& x) const
+ { return multiply(x, this->square(x)); }
+
bool initialized() const { return (mod_words != 0); }
Modular_Reducer() { mod_words = 0; }
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 18:22:17 +0000