OKlibrary  0.2.1.6
Algebra_Models.hpp
Go to the documentation of this file.
```00001 // Oliver Kullmann, 6.11.2004 (Swansea)
00002 /* Copyright 2004 - 2007 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007
00018 #ifndef ALGEBRAWAECHTER_jbbZ3y7
00019
00020 #define ALGEBRAWAECHTER_jbbZ3y7
00021
00022 #include <functional>
00023 #include <cassert>
00024 #include <ostream>
00025
00026 #include <OKlib/General/NumberTheory_Models.hpp>
00027 #include <OKlib/General/Algorithms.hpp>
00028
00029 namespace Algebra {
00030
00031   // OK, 7.11.2004
00032   template <typename Int>
00033   struct Normed_remainder : std::unary_function<Int, Int> {
00034     const Int n;
00035     Normed_remainder(const Int n) : n(n) {
00036       assert(n > 0);
00037     }
00038     Int operator() (Int x) const {
00039       if (x < 0) {
00040         x = -x; x %= n;
00041         if (x != 0)
00042           x = n - x;
00043       }
00044       else
00045         x %= n;
00046       assert(x >= 0);
00047       assert(x < n);
00048       return x;
00049     }
00050   };
00051   template <typename Int>
00052   inline Int normed_remainder(const Int x, const Int n) {
00053     return (Normed_remainder<Int>(n))(x);
00054   }
00055
00056   // #####################################################
00057
00058   template <unsigned long int modulus, typename Int>
00059   class Z_mod_n {
00060     // TO IMPROVE: Generalising "unsigned long int".
00061     // TO IMPROVE: Recognising moduli which are too large (at compile time).
00062     Int x;
00063     typedef NumberTheory::Gcd_extended<Int> Gcd_e;
00064   public :
00065     Z_mod_n() : x(Int(0)) {}
00066     explicit Z_mod_n(Int x) : x(normed_remainder(x, Int(modulus))) {}
00067
00068     Z_mod_n& operator +=(Z_mod_n y) {
00069       assert(x >= 0);
00070       assert(x < Int(modulus));
00071       x += y.x;
00072       if (x >= Int(modulus))
00073         x -= Int(modulus);
00074       return *this;
00075     }
00076     Z_mod_n& operator *=(Z_mod_n y) {
00077       assert(x >= 0);
00078       assert(x < Int(modulus));
00079       x *= y.x;
00080       x %= Int(modulus);
00081       return *this;
00082     }
00083     Z_mod_n& operator -=(Z_mod_n y) {
00084       assert(x >= 0);
00085       assert(x < Int(modulus));
00086       x -= y.x;
00087       if (x < Int(0))
00088         x += Int(modulus);
00089       return *this;
00090     }
00091     bool invert() {
00092       assert(x >= 0);
00093       assert(x < Int(modulus));
00094       const typename Gcd_e::result_type gcd_extended = Gcd_e()(x, Int(modulus));
00095       if (gcd_extended.c != Int(1))
00096         return false;
00097       x = gcd_extended.x;
00098       if (x < Int(0))
00099         x += Int(modulus);
00100       return true;
00101     }
00102     Z_mod_n& operator /=(Z_mod_n y) {
00103       assert(x >= 0);
00104       assert(x < Int(modulus));
00105       const bool invertible = y.invert();
00106       assert(invertible);
00107       x *= y.x;
00108       x %= Int(modulus);
00109       return *this;
00110     }
00111     static const Z_mod_n null() {
00112       return Z_mod_n(Int(0));
00113     }
00114     static const Z_mod_n unit() {
00115       return Z_mod_n(Int(1));
00116     }
00117
00118     friend inline bool operator ==(const Z_mod_n lhs, const Z_mod_n rhs) {
00119       return lhs.x == rhs.x;
00120     }
00121
00122     friend inline std::ostream& operator <<(std::ostream& out, Z_mod_n<modulus, Int> x) {
00123       return out << x.x;
00124     }
00125
00126   };
00127
00128   template <unsigned long int modulus, typename Int>
00129   inline Z_mod_n<modulus, Int> operator +(const Z_mod_n<modulus, Int> a, const Z_mod_n<modulus, Int> b) {
00130     Z_mod_n<modulus, Int> r(a);
00131     r += b;
00132     return r;
00133   }
00134   template <unsigned long int modulus, typename Int>
00135   inline Z_mod_n<modulus, Int> operator *(const Z_mod_n<modulus, Int> a, const Z_mod_n<modulus, Int> b) {
00136     Z_mod_n<modulus, Int> r(a);
00137     r *= b;
00138     return r;
00139   }
00140   template <unsigned long int modulus, typename Int>
00141   inline Z_mod_n<modulus, Int> operator -(const Z_mod_n<modulus, Int> a, const Z_mod_n<modulus, Int> b) {
00142     Z_mod_n<modulus, Int> r(a);
00143     r -= b;
00144     return r;
00145   }
00146   template <unsigned long int modulus, typename Int>
00147   inline Z_mod_n<modulus, Int> operator -(const Z_mod_n<modulus, Int> a) {
00148     Z_mod_n<modulus, Int> r(Int(0));
00149     r -= a;
00150     return r;
00151   }
00152   template <unsigned long int modulus, typename Int>
00153   inline Z_mod_n<modulus, Int> operator /(const Z_mod_n<modulus, Int> a, const Z_mod_n<modulus, Int> b) {
00154     assert((Z_mod_n<modulus, Int>(b).invert()));
00155     Z_mod_n<modulus, Int> r(a);
00156     r /= b;
00157     return r;
00158   }
00159
00160   template <unsigned long int modulus, typename Int>
00161   inline bool operator !=(const Z_mod_n<modulus, Int> a, const Z_mod_n<modulus, Int> b) {
00162     return not(a == b);
00163   }
00164
00165
00166 }
00167
00168 namespace Algebra_Traits {
00169
00170   template <unsigned long int modulus, typename Int>
00171   struct MultiplicativeGroupoid_traits<Algebra::Z_mod_n<modulus, Int> > {
00172     typedef Algebra::Z_mod_n<modulus, Int> value_type;
00173     static value_type identity() { return value_type(1); }
00174     static bool invertible(value_type x) { return x.invert(); }
00175     static value_type inverse (value_type x) {
00176       const bool invertible = x.invert();
00177       assert(invertible);
00178       return x;
00179     }
00180   };
00181 }
00182
00183 // #####################################################
00184
00185 namespace Algebra {
00186
00187   template <typename Int = long int>
00188   class Zmodn {
00189     // TO IMPROVE: Needs proper design.
00190     Int x;
00191     typedef NumberTheory::Gcd_extended<Int> Gcd_e;
00192   public :
00193     static Int modulus;
00194     Zmodn() : x(Int(0)) {}
00195     explicit Zmodn(Int x) : x(normed_remainder(x, Int(modulus))) {}
00196     Int rem() const { return x; }
00197
00198     Zmodn& operator +=(Zmodn y) {
00199       assert(x >= 0);
00200       assert(x < Int(modulus));
00201       x += y.x;
00202       if (x >= Int(modulus))
00203         x -= Int(modulus);
00204       return *this;
00205     }
00206     Zmodn& operator *=(Zmodn y) {
00207       assert(x >= 0);
00208       assert(x < Int(modulus));
00209       x *= y.x;
00210       x %= Int(modulus);
00211       return *this;
00212     }
00213     Zmodn& operator -=(Zmodn y) {
00214       assert(x >= 0);
00215       assert(x < Int(modulus));
00216       x -= y.x;
00217       if (x < Int(0))
00218         x += Int(modulus);
00219       return *this;
00220     }
00221     bool invert() {
00222       assert(x >= 0);
00223       assert(x < Int(modulus));
00224       const typename Gcd_e::result_type gcd_extended = Gcd_e()(x, Int(modulus));
00225       if (gcd_extended.c != Int(1))
00226         return false;
00227       x = gcd_extended.x;
00228       if (x < Int(0))
00229         x += Int(modulus);
00230       return true;
00231     }
00232     Zmodn& operator /=(Zmodn y) {
00233       assert(x >= 0);
00234       assert(x < Int(modulus));
00235       assert(y.invert());
00236       x *= y.x;
00237       x %= Int(modulus);
00238       return *this;
00239     }
00240     static const Zmodn null() {
00241       return Zmodn(Int(0));
00242     }
00243     static const Zmodn unit() {
00244       return Zmodn(Int(1));
00245     }
00246
00247     friend inline bool operator ==(const Zmodn lhs, const Zmodn rhs) {
00248       return lhs.x == rhs.x;
00249     }
00250
00251     friend inline std::ostream& operator <<(std::ostream& out, Zmodn<Int> x) {
00252       return out << x.x;
00253     }
00254
00255   };
00256
00257    template <typename Int>
00258    Int Zmodn<Int>::modulus(1);
00259
00260   template <typename Int>
00261   inline Zmodn<Int> operator +(const Zmodn<Int> a, const Zmodn<Int> b) {
00262     Zmodn<Int> r(a);
00263     r += b;
00264     return r;
00265   }
00266   template <typename Int>
00267   inline Zmodn<Int> operator *(const Zmodn<Int> a, const Zmodn<Int> b) {
00268     Zmodn<Int> r(a);
00269     r *= b;
00270     return r;
00271   }
00272   template <typename Int>
00273   inline Zmodn<Int> operator -(const Zmodn<Int> a, const Zmodn<Int> b) {
00274     Zmodn<Int> r(a);
00275     r -= b;
00276     return r;
00277   }
00278   template <typename Int>
00279   inline Zmodn<Int> operator -(const Zmodn<Int> a) {
00280     Zmodn<Int> r(Int(0));
00281     r -= a;
00282     return r;
00283   }
00284   template <typename Int>
00285   inline Zmodn<Int> operator /(const Zmodn<Int> a, const Zmodn<Int> b) {
00286     assert((Zmodn<Int>(b).invert()));
00287     Zmodn<Int> r(a);
00288     r /= b;
00289     return r;
00290   }
00291
00292   template <typename Int>
00293   inline bool operator !=(const Zmodn<Int> a, const Zmodn<Int> b) {
00294     return not(a == b);
00295   }
00296
00297
00298 }
00299
00300 namespace Algebra_Traits {
00301
00302   template <typename Int>
00303   struct MultiplicativeGroupoid_traits<Algebra::Zmodn<Int> > {
00304     typedef Algebra::Zmodn<Int> value_type;
00305     static value_type identity() { return value_type(1); }
00306     static bool invertible(value_type x) { return x.invert(); }
00307     static value_type inverse (value_type x) {
00308       const bool invertible = x.invert();
00309       assert(invertible);
00310       return x;
00311     }
00312   };
00313 }
00314
00315 // #####################################################
00316
00317 namespace Algebra {
00318
00319   template <typename Int = long int>
00320   struct RSA {
00321
00322     typedef Int int_type;
00323     const int_type p, q;
00324     const int_type n, N;
00325
00326     typedef Zmodn<Int> mod_type; // We need *two* different types or objects here (for the 2 moduli) !
00327     bool dummy;
00328
00329     const mod_type e, d;
00330
00331     RSA(const int_type p_, const int_type q_, const int_type e_) : p(p_), q(q_), n(p * q), N((p-1) * (q-1)), dummy(set_temp_modulus()), e(e_), d(mod_type(1) / e) {
00332       // assert p, q are prime numbers
00333       mod_type::modulus = n;
00334     }
00335
00336     mod_type encrypt(const int_type plaintext) const {
00337       return Algorithms::power_natural(mod_type(plaintext), e.rem());
00338     }
00339     mod_type decrypt(const int_type plaintext) const {
00340       return Algorithms::power_natural(mod_type(plaintext), d.rem());
00341     }
00342
00343   private :
00344
00345     bool set_temp_modulus() {
00346       mod_type::modulus = N;
00347       return true;
00348     }
00349   };
00350
00351 }
00352
00353 #endif
```