1 #ifndef CRYPTOPP_GF2N_H
2 #define CRYPTOPP_GF2N_H
13 NAMESPACE_BEGIN(CryptoPP)
29 typedef unsigned int RandomizationParameter;
37 PolynomialMod2(
const PolynomialMod2& t);
44 PolynomialMod2(word value,
size_t bitLength=WORD_BITS);
48 {Decode(encodedPoly, byteCount);}
52 {Decode(encodedPoly, byteCount);}
56 {Randomize(rng, bitcount);}
59 static PolynomialMod2 CRYPTOPP_API Monomial(
size_t i);
61 static PolynomialMod2 CRYPTOPP_API Trinomial(
size_t t0,
size_t t1,
size_t t2);
63 static PolynomialMod2 CRYPTOPP_API Pentanomial(
size_t t0,
size_t t1,
size_t t2,
size_t t3,
size_t t4);
65 static PolynomialMod2 CRYPTOPP_API AllOnes(
size_t n);
68 static const PolynomialMod2 & CRYPTOPP_API Zero();
70 static const PolynomialMod2 & CRYPTOPP_API One();
83 void Encode(byte *output,
size_t outputLen)
const;
88 void Decode(
const byte *input,
size_t inputLen);
102 unsigned int BitCount()
const;
104 unsigned int ByteCount()
const;
106 unsigned int WordCount()
const;
109 bool GetBit(
size_t n)
const {
return GetCoefficient(n)!=0;}
111 byte GetByte(
size_t n)
const;
114 signed int Degree()
const {
return BitCount()-1;}
119 {
return (i/WORD_BITS < reg.size()) ?
int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
121 int operator[](
unsigned int i)
const {
return GetCoefficient(i);}
124 bool IsZero()
const {
return !*
this;}
126 bool Equals(
const PolynomialMod2 &rhs)
const;
132 PolynomialMod2& operator=(
const PolynomialMod2& t);
134 PolynomialMod2& operator&=(
const PolynomialMod2& t);
136 PolynomialMod2& operator^=(
const PolynomialMod2& t);
138 PolynomialMod2& operator+=(
const PolynomialMod2& t) {
return *
this ^= t;}
140 PolynomialMod2& operator-=(
const PolynomialMod2& t) {
return *
this ^= t;}
142 PolynomialMod2& operator*=(
const PolynomialMod2& t);
144 PolynomialMod2& operator/=(
const PolynomialMod2& t);
146 PolynomialMod2& operator%=(
const PolynomialMod2& t);
148 PolynomialMod2& operator<<=(
unsigned int);
150 PolynomialMod2& operator>>=(
unsigned int);
156 void SetBit(
size_t i,
int value = 1);
158 void SetByte(
size_t n, byte value);
161 void SetCoefficient(
size_t i,
int value) {SetBit(i, value);}
164 void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
170 bool operator!()
const;
172 PolynomialMod2 operator+()
const {
return *
this;}
174 PolynomialMod2 operator-()
const {
return *
this;}
180 PolynomialMod2 And(
const PolynomialMod2 &b)
const;
182 PolynomialMod2 Xor(
const PolynomialMod2 &b)
const;
184 PolynomialMod2 Plus(
const PolynomialMod2 &b)
const {
return Xor(b);}
186 PolynomialMod2 Minus(
const PolynomialMod2 &b)
const {
return Xor(b);}
188 PolynomialMod2 Times(
const PolynomialMod2 &b)
const;
190 PolynomialMod2 DividedBy(
const PolynomialMod2 &b)
const;
192 PolynomialMod2 Modulo(
const PolynomialMod2 &b)
const;
195 PolynomialMod2 operator>>(
unsigned int n)
const;
197 PolynomialMod2 operator<<(
unsigned int n)
const;
203 unsigned int Parity()
const;
206 bool IsIrreducible()
const;
209 PolynomialMod2
Doubled()
const {
return Zero();}
211 PolynomialMod2 Squared()
const;
214 bool IsUnit()
const {
return Equals(One());}
219 static PolynomialMod2 CRYPTOPP_API Gcd(
const PolynomialMod2 &a,
const PolynomialMod2 &n);
221 PolynomialMod2 InverseMod(
const PolynomialMod2 &)
const;
224 static void CRYPTOPP_API Divide(PolynomialMod2 &r, PolynomialMod2 &q,
const PolynomialMod2 &a,
const PolynomialMod2 &d);
230 friend std::ostream& operator<<(std::ostream& out,
const PolynomialMod2 &a);
240 inline bool operator==(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
241 {
return a.Equals(b);}
243 inline bool operator!=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
246 inline bool operator> (
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
247 {
return a.Degree() > b.Degree();}
249 inline bool operator>=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
250 {
return a.Degree() >= b.Degree();}
252 inline bool operator< (
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
253 {
return a.Degree() < b.Degree();}
255 inline bool operator<=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
256 {
return a.Degree() <= b.Degree();}
258 inline CryptoPP::PolynomialMod2 operator&(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.And(b);}
260 inline CryptoPP::PolynomialMod2 operator^(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Xor(b);}
262 inline CryptoPP::PolynomialMod2 operator+(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Plus(b);}
264 inline CryptoPP::PolynomialMod2 operator-(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Minus(b);}
266 inline CryptoPP::PolynomialMod2 operator*(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Times(b);}
268 inline CryptoPP::PolynomialMod2 operator/(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.DividedBy(b);}
270 inline CryptoPP::PolynomialMod2 operator%(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Modulo(b);}
284 GF2NP(
const PolynomialMod2 &modulus);
286 virtual GF2NP * Clone()
const {
return new GF2NP(*
this);}
293 bool Equal(
const Element &a,
const Element &b)
const
294 {assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree());
return a.Equals(b);}
296 bool IsUnit(
const Element &a)
const
297 {assert(a.Degree() < m_modulus.Degree());
return !!a;}
299 unsigned int MaxElementBitLength()
const
302 unsigned int MaxElementByteLength()
const
303 {
return (
unsigned int)BitsToBytes(MaxElementBitLength());}
305 Element SquareRoot(
const Element &a)
const;
307 Element HalfTrace(
const Element &a)
const;
310 Element SolveQuadraticEquation(
const Element &a)
const;
321 GF2NT(
unsigned int t0,
unsigned int t1,
unsigned int t2);
323 GF2NP * Clone()
const {
return new GF2NT(*
this);}
326 const Element& Multiply(
const Element &a,
const Element &b)
const;
328 const Element&
Square(
const Element &a)
const
329 {
return Reduced(a.Squared());}
331 const Element& MultiplicativeInverse(
const Element &a)
const;
334 const Element& Reduced(
const Element &a)
const;
337 mutable PolynomialMod2 result;
345 GF2NPP(
unsigned int t0,
unsigned int t1,
unsigned int t2,
unsigned int t3,
unsigned int t4)
352 unsigned int t0, t1, t2, t3;
362 template<> inline
void swap(CryptoPP::PolynomialMod2 &a, CryptoPP::PolynomialMod2 &b)
base class for all exceptions thrown by Crypto++
bool operator>=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
bool operator>(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
PolynomialMod2 Doubled() const
is always zero since we're working modulo 2
GF(2^n) with Trinomial Basis.
int GetCoefficient(size_t i) const
return coefficient for x^i
signed int Degree() const
the zero polynomial will return a degree of -1
interface for random number generators
Polynomial with Coefficients in GF(2)
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
PolynomialMod2(BufferedTransformation &encodedPoly, size_t byteCount)
convert from big-endian form stored in a BufferedTransformation
int operator[](unsigned int i) const
return coefficient for x^i
bool IsUnit() const
only 1 is a unit
unsigned int MinEncodedSize() const
minimum number of bytes to encode this polynomial
PolynomialMod2(const byte *encodedPoly, size_t byteCount)
convert from big-endian byte array
bool operator<(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
bool GetBit(size_t n) const
return the n-th bit, n=0 being the least significant bit
GF(2^n) with Pentanomial Basis.
static PolynomialMod2 Pentanomial(size_t t0, size_t t1, size_t t2, size_t t3, size_t t4)
return x^t0 + x^t1 + x^t2 + x^t3 + x^t4
GF(2^n) with Polynomial Basis.
PolynomialMod2(RandomNumberGenerator &rng, size_t bitcount)
create a random polynomial uniformly distributed over all polynomials with degree less than bitcount ...
unsigned int CoefficientCount() const
degree + 1
bool operator<=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree