1 #ifndef CRYPTOPP_GF2N_H 2 #define CRYPTOPP_GF2N_H 30 typedef unsigned int RandomizationParameter;
38 PolynomialMod2(
const PolynomialMod2& t);
45 PolynomialMod2(word value,
size_t bitLength=WORD_BITS);
49 {Decode(encodedPoly, byteCount);}
53 {Decode(encodedPoly, byteCount);}
57 {Randomize(rng, bitcount);}
60 static PolynomialMod2 CRYPTOPP_API Monomial(
size_t i);
62 static PolynomialMod2 CRYPTOPP_API Trinomial(
size_t t0,
size_t t1,
size_t t2);
64 static PolynomialMod2 CRYPTOPP_API Pentanomial(
size_t t0,
size_t t1,
size_t t2,
size_t t3,
size_t t4);
66 static PolynomialMod2 CRYPTOPP_API AllOnes(
size_t n);
69 static const PolynomialMod2 & CRYPTOPP_API Zero();
71 static const PolynomialMod2 & CRYPTOPP_API One();
84 void Encode(byte *output,
size_t outputLen)
const;
89 void Decode(
const byte *input,
size_t inputLen);
103 unsigned int BitCount()
const;
105 unsigned int ByteCount()
const;
107 unsigned int WordCount()
const;
110 bool GetBit(
size_t n)
const {
return GetCoefficient(n)!=0;}
115 signed int Degree()
const {
return (
signed int)(BitCount()-1U);}
120 {
return (i/WORD_BITS < reg.size()) ?
int(reg[i/WORD_BITS] >> (i % WORD_BITS)) & 1 : 0;}
122 int operator[](
unsigned int i)
const {
return GetCoefficient(i);}
125 bool IsZero()
const {
return !*
this;}
127 bool Equals(
const PolynomialMod2 &rhs)
const;
133 PolynomialMod2& operator=(
const PolynomialMod2& t);
135 PolynomialMod2& operator&=(
const PolynomialMod2& t);
137 PolynomialMod2& operator^=(
const PolynomialMod2& t);
139 PolynomialMod2& operator+=(
const PolynomialMod2& t) {
return *
this ^= t;}
141 PolynomialMod2& operator-=(
const PolynomialMod2& t) {
return *
this ^= t;}
143 PolynomialMod2& operator*=(
const PolynomialMod2& t);
145 PolynomialMod2& operator/=(
const PolynomialMod2& t);
147 PolynomialMod2& operator%=(
const PolynomialMod2& t);
149 PolynomialMod2& operator<<=(
unsigned int);
151 PolynomialMod2& operator>>=(
unsigned int);
157 void SetBit(
size_t i,
int value = 1);
159 void SetByte(
size_t n, byte value);
162 void SetCoefficient(
size_t i,
int value) {SetBit(i, value);}
165 void swap(PolynomialMod2 &a) {reg.swap(a.reg);}
171 bool operator!()
const;
173 PolynomialMod2 operator+()
const {
return *
this;}
175 PolynomialMod2 operator-()
const {
return *
this;}
181 PolynomialMod2 And(
const PolynomialMod2 &b)
const;
183 PolynomialMod2 Xor(
const PolynomialMod2 &b)
const;
185 PolynomialMod2 Plus(
const PolynomialMod2 &b)
const {
return Xor(b);}
187 PolynomialMod2 Minus(
const PolynomialMod2 &b)
const {
return Xor(b);}
189 PolynomialMod2 Times(
const PolynomialMod2 &b)
const;
191 PolynomialMod2 DividedBy(
const PolynomialMod2 &b)
const;
193 PolynomialMod2 Modulo(
const PolynomialMod2 &b)
const;
196 PolynomialMod2 operator>>(
unsigned int n)
const;
198 PolynomialMod2 operator<<(
unsigned int n)
const;
204 unsigned int Parity()
const;
207 bool IsIrreducible()
const;
210 PolynomialMod2
Doubled()
const {
return Zero();}
212 PolynomialMod2 Squared()
const;
215 bool IsUnit()
const {
return Equals(One());}
220 static PolynomialMod2 CRYPTOPP_API Gcd(
const PolynomialMod2 &a,
const PolynomialMod2 &n);
222 PolynomialMod2 InverseMod(
const PolynomialMod2 &)
const;
225 static void CRYPTOPP_API Divide(PolynomialMod2 &r, PolynomialMod2 &q,
const PolynomialMod2 &a,
const PolynomialMod2 &d);
231 friend std::ostream& operator<<(std::ostream& out,
const PolynomialMod2 &a);
241 inline bool operator==(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
242 {
return a.Equals(b);}
244 inline bool operator!=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
247 inline bool operator> (
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
248 {
return a.Degree() > b.Degree();}
250 inline bool operator>=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
251 {
return a.Degree() >= b.Degree();}
253 inline bool operator< (
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
254 {
return a.Degree() < b.Degree();}
256 inline bool operator<=(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b)
257 {
return a.Degree() <= b.Degree();}
259 inline CryptoPP::PolynomialMod2 operator&(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.And(b);}
261 inline CryptoPP::PolynomialMod2 operator^(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Xor(b);}
263 inline CryptoPP::PolynomialMod2 operator+(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Plus(b);}
265 inline CryptoPP::PolynomialMod2 operator-(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Minus(b);}
267 inline CryptoPP::PolynomialMod2
operator*(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Times(b);}
269 inline CryptoPP::PolynomialMod2 operator/(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.DividedBy(b);}
271 inline CryptoPP::PolynomialMod2 operator%(
const CryptoPP::PolynomialMod2 &a,
const CryptoPP::PolynomialMod2 &b) {
return a.Modulo(b);}
287 virtual GF2NP * Clone()
const {
return new GF2NP(*
this);}
289 {CRYPTOPP_UNUSED(bt); assert(
false);}
294 bool Equal(
const Element &a,
const Element &b)
const 295 {assert(a.Degree() < m_modulus.Degree() && b.Degree() < m_modulus.Degree());
return a.Equals(b);}
297 bool IsUnit(
const Element &a)
const 298 {assert(a.Degree() < m_modulus.Degree());
return !!a;}
300 unsigned int MaxElementBitLength()
const 303 unsigned int MaxElementByteLength()
const 304 {
return (
unsigned int)
BitsToBytes(MaxElementBitLength());}
306 Element SquareRoot(
const Element &a)
const;
308 Element HalfTrace(
const Element &a)
const;
311 Element SolveQuadraticEquation(
const Element &a)
const;
322 GF2NT(
unsigned int t0,
unsigned int t1,
unsigned int t2);
324 GF2NP * Clone()
const {
return new GF2NT(*
this);}
327 const Element& Multiply(
const Element &a,
const Element &b)
const;
329 const Element&
Square(
const Element &a)
const 330 {
return Reduced(a.Squared());}
332 const Element& MultiplicativeInverse(
const Element &a)
const;
335 const Element& Reduced(
const Element &a)
const;
346 GF2NPP(
unsigned int t0,
unsigned int t1,
unsigned int t2,
unsigned int t3,
unsigned int t4)
353 unsigned int t0, t1, t2, t3;
363 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
inline::Integer operator*(const ::Integer &a, const ::Integer &b)
Utility functions for the Crypto++ library.
PolynomialMod2 Doubled() const
is always zero since we're working modulo 2
size_t BitsToBytes(size_t bitCount)
Returns the number of 8-bit bytes or octets required for the specified number of bits.
GF(2^n) with Trinomial Basis.
int GetCoefficient(size_t i) const
return coefficient for x^i
Abstract base classes that provide a uniform interface to this library.
signed int Degree() const
the zero polynomial will return a degree of -1
Interface for random number generators.
Classes for performing mathematics over different fields.
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
Classes and functions for secure memory allocations.
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
unsigned int Parity(T value)
Returns the parity of a value.
bool GetBit(size_t n) const
return the n-th bit, n=0 being the least significant bit
Classes and functions for working with ANS.1 objects.
GF(2^n) with Pentanomial Basis.
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 ...
const T & STDMAX(const T &a, const T &b)
Replacement function for std::max.
unsigned int CoefficientCount() const
degree + 1
Crypto++ library namespace.
unsigned int GetByte(ByteOrder order, T value, unsigned int index)
Gets a byte from a value.
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
SecWordBlock is a SecBlock<word> typedef.
bool operator<=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree