FiniteFieldElement.hpp

00001 
00002 
00003 namespace Cryptography
00004 {
00005        // helper functions
00006         namespace   detail
00007         {            
00008             //From Knuth; Extended GCD gives g = a*u + b*v
00009             int EGCD(int a, int b, int& u, int &v)
00010             { 
00011                 u = 1; 
00012                 v = 0; 
00013                 int g = a; 
00014                 int u1 = 0;
00015                 int v1 = 1; 
00016                 int g1 = b; 
00017                 while (g1 != 0) 
00018                 { 
00019                     int q = g/g1; // Integer divide 
00020                     int t1 = u - q*u1; 
00021                     int t2 = v - q*v1; 
00022                     int t3 = g - q*g1; 
00023                     u = u1; v = v1; g = g1; 
00024                     u1 = t1; v1 = t2; g1 = t3; 
00025                 } 
00026                 
00027                 return g;
00028             }
00029             
00030             int InvMod(int x, int n) // Solve linear congruence equation x * z == 1 (mod n) for z 
00031             { 
00032                 //n = Abs(n); 
00033                 x = x % n; // % is the remainder function, 0 <= x % n < |n| 
00034                 int u,v,g,z;
00035                 g = EGCD(x, n, u,v);
00036                 if (g != 1) 
00037                 { 
00038                     // x and n have to be relative prime for there to exist an x^-1 mod n
00039                     z = 0; 
00040                 } 
00041                 else 
00042                 { 
00043                     z = u % n;
00044                 } 
00045                 return z;
00046             }
00047         }
00048         
00049         /*
00050             An element in a Galois field FP
00051             Adapted for the specific behaviour of the "mod" function where (-n) mod m returns a negative number
00052             Allows basic arithmetic operations between elements:
00053                 +,-,/,scalar multiply                
00054                 
00055             The template argument P is the order of the field
00056         */
00057         template<int P>
00058         class   FiniteFieldElement
00059         {
00060             int     i_;
00061             
00062             void    assign(int i)
00063             {
00064                 i_ = i;
00065                 if ( i<0 )
00066                 {                    
00067                     // ensure (-i) mod p correct behaviour
00068                     // the (i%P) term is to ensure that i is in the correct range before normalizing
00069                     i_ = (i%P) + 2*P;
00070                 }
00071 
00072                 i_ %= P;
00073             }
00074             
00075             public:
00076                 // ctor
00077                 FiniteFieldElement()
00078                  : i_(0)
00079                 {}
00080                 // ctor
00081                 explicit FiniteFieldElement(int i)
00082                 {
00083                     assign(i);
00084                 }
00085                 // copy ctor
00086                 FiniteFieldElement(const FiniteFieldElement<P>& rhs) 
00087                  : i_(rhs.i_)               
00088                 {
00089                 }
00090                 
00091                 // access "raw" integer
00092                 int i() const { return i_; }                
00093                 // negate
00094                 FiniteFieldElement  operator-() const
00095                 {
00096                     return FiniteFieldElement(-i_);
00097                 }                                
00098                 // assign from integer
00099                 FiniteFieldElement& operator=(int i)
00100                 {
00101                     assign(i);
00102                     return *this;
00103                 }
00104                 // assign from field element
00105                 FiniteFieldElement<P>& operator=(const FiniteFieldElement<P>& rhs)
00106                 {
00107                     i_ = rhs.i_;
00108                     return *this;
00109                 }
00110                 // *=
00111                 FiniteFieldElement<P>& operator*=(const FiniteFieldElement<P>& rhs)
00112                 {
00113                     i_ = (i_*rhs.i_) % P;
00114                     return *this;           
00115                 }
00116                 // ==
00117                 friend bool    operator==(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
00118                 {
00119                     return (lhs.i_ == rhs.i_);
00120                 }
00121                 // == int
00122                 friend bool    operator==(const FiniteFieldElement<P>& lhs, int rhs)
00123                 {
00124                     return (lhs.i_ == rhs);
00125                 }
00126                 // !=
00127                 friend bool    operator!=(const FiniteFieldElement<P>& lhs, int rhs)
00128                 {
00129                     return (lhs.i_ != rhs);
00130                 }                
00131                 // a / b
00132                 friend FiniteFieldElement<P> operator/(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
00133                 {
00134                     return FiniteFieldElement<P>( lhs.i_ * detail::InvMod(rhs.i_,P));
00135                 }
00136                 // a + b
00137                 friend FiniteFieldElement<P> operator+(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
00138                 {
00139                     return FiniteFieldElement<P>( lhs.i_ + rhs.i_);
00140                 }
00141                 // a - b
00142                 friend FiniteFieldElement<P> operator-(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
00143                 {
00144                     return FiniteFieldElement<P>( lhs.i_ - rhs.i_);
00145                 }
00146                 // a + int
00147                 friend FiniteFieldElement<P> operator+(const FiniteFieldElement<P>& lhs, int i)
00148                 {
00149                     return FiniteFieldElement<P>( lhs.i_+i);
00150                 }
00151                 // int + a
00152                 friend FiniteFieldElement<P> operator+(int i, const FiniteFieldElement<P>& rhs)
00153                 {
00154                     return FiniteFieldElement<P>( rhs.i_+i);
00155                 }
00156                 // int * a
00157                 friend FiniteFieldElement<P> operator*(int n, const FiniteFieldElement<P>& rhs)
00158                 {
00159                     return FiniteFieldElement<P>( n*rhs.i_);
00160                 }                
00161                 // a * b
00162                 friend FiniteFieldElement<P> operator*(const FiniteFieldElement<P>& lhs, const FiniteFieldElement<P>& rhs)
00163                 {
00164                     return FiniteFieldElement<P>( lhs.i_ * rhs.i_);
00165                 }
00166                 // ostream handler
00167                 template<int T>
00168                 friend  ostream&    operator<<(ostream& os, const FiniteFieldElement<T>& g)
00169                 {
00170                     return os << g.i_;
00171                 }
00172         };
00173 }
00174 
00175