6 #ifndef CRYPTOPP_IMPORTS 30 assert(value==0 || reg.
size()>0);
35 SetWords(reg+1, 0, reg.
size()-1);
42 CopyWords(reg, t.reg, reg.
size());
47 const size_t nbytes = nbits/8 + 1;
50 buf[0] = (byte)
Crop(buf[0], nbits % 8);
58 if (bitLength%WORD_BITS)
59 result.reg[result.reg.
size()-1] = (word)
Crop(result.reg[result.reg.
size()-1], bitLength%WORD_BITS);
63 void PolynomialMod2::SetBit(
size_t n,
int value)
68 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
72 if (n/WORD_BITS < reg.
size())
73 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
79 if (n/WORD_SIZE >= reg.
size())
82 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
88 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
89 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
138 void PolynomialMod2::Decode(
const byte *input,
size_t inputLen)
141 Decode(store, inputLen);
154 for (
size_t i=inputLen; i > 0; i--)
158 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
164 for (
size_t i=outputLen; i > 0; i--)
178 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
186 return (
unsigned int)CountWords(reg, reg.size());
193 return (wordCount-1)*WORD_SIZE +
BytePrecision(reg[wordCount-1]);
202 return (wordCount-1)*WORD_BITS +
BitPrecision(reg[wordCount-1]);
211 for (i=0; i<reg.size(); i++)
224 reg.CleanGrow(t.reg.
size());
225 XorWords(reg, t.reg, t.reg.
size());
231 if (b.reg.
size() >= reg.size())
234 XorWords(result.reg, reg, b.reg, reg.
size());
235 CopyWords(result.reg+reg.size(), b.reg+reg.
size(), b.reg.
size()-reg.size());
241 XorWords(result.reg, reg, b.reg, b.reg.
size());
242 CopyWords(result.reg+b.reg.
size(), reg+b.reg.
size(), reg.size()-b.reg.
size());
250 AndWords(result.reg, reg, b.reg, result.reg.
size());
258 for (
int i=b.
Degree(); i>=0; i--)
262 XorWords(result.reg, reg, reg.size());
269 static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};
273 for (
unsigned i=0; i<reg.size(); i++)
277 for (j=0; j<WORD_BITS; j+=8)
278 result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
280 for (j=0; j<WORD_BITS; j+=8)
281 result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j;
293 int degree = divisor.
Degree();
300 for (
int i=dividend.
Degree(); i>=0; i--)
303 remainder.reg[0] |= dividend[i];
304 if (remainder[degree])
306 remainder -= divisor;
329 int x; CRYPTOPP_UNUSED(x);
347 *r = (u << 1) | carry;
348 carry = u >> (WORD_BITS-1);
354 reg.Grow(reg.size()+1);
355 reg[reg.size()-1] = carry;
361 const int shiftWords = n / WORD_BITS;
362 const int shiftBits = n % WORD_BITS;
370 *r = (u << shiftBits) | carry;
371 carry = u >> (WORD_BITS-shiftBits);
379 const size_t carryIndex = reg.size();
380 reg.Grow(reg.size()+shiftWords+!!shiftBits);
381 reg[carryIndex] = carry;
384 reg.Grow(reg.size()+shiftWords);
388 for (i = (
int)reg.size()-1; i>=shiftWords; i--)
389 reg[i] = reg[i-shiftWords];
402 int shiftWords = n / WORD_BITS;
403 int shiftBits = n % WORD_BITS;
408 word *r=reg+reg.size()-1;
416 *r = (u >> shiftBits) | carry;
417 carry = u << (WORD_BITS-shiftBits);
424 for (i=0; i<reg.size()-shiftWords; i++)
425 reg[i] = reg[i+shiftWords];
426 for (; i<reg.size(); i++)
445 bool PolynomialMod2::operator!()
const 447 for (
unsigned i=0; i<reg.size(); i++)
448 if (reg[i])
return false;
454 size_t i, smallerSize =
STDMIN(reg.size(), rhs.reg.
size());
456 for (i=0; i<smallerSize; i++)
457 if (reg[i] != rhs.reg[i])
return false;
459 for (i=smallerSize; i<reg.size(); i++)
460 if (reg[i] != 0)
return false;
462 for (i=smallerSize; i<rhs.reg.
size(); i++)
463 if (rhs.reg[i] != 0)
return false;
468 std::ostream& operator<<(std::ostream& out,
const PolynomialMod2 &a)
471 long f = out.flags() & std::ios::basefield;
493 return out <<
'0' << suffix;
498 static const char upper[]=
"0123456789ABCDEF";
499 static const char lower[]=
"0123456789abcdef";
500 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
502 for (i=0; i*bits < a.
BitCount(); i++)
505 for (
int j=0; j<bits; j++)
506 digit |= a[i*bits+j] << j;
513 if (i && (i%block)==0)
517 return out << suffix;
538 for (
int i=1; i<=d/2; i++)
540 u = u.Squared()%(*this);
554 GF2NP::Element GF2NP::SquareRoot(
const Element &a)
const 557 for (
unsigned int i=1; i<m; i++)
562 GF2NP::Element GF2NP::HalfTrace(
const Element &a)
const 566 for (
unsigned int i=1; i<=(m-1)/2; i++)
571 GF2NP::Element GF2NP::SolveQuadraticEquation(
const Element &a)
const 580 z = PolynomialMod2::Zero();
582 for (
unsigned int i=1; i<=m-1; i++)
586 Accumulate(z, Multiply(w, a));
589 }
while (w.IsZero());
598 GF2NT::GF2NT(
unsigned int t0,
unsigned int t1,
unsigned int t2)
603 assert(t0 > t1 && t1 > t2 && t2==0);
606 const GF2NT::Element& GF2NT::MultiplicativeInverse(
const Element &a)
const 608 if (t0-t1 < WORD_BITS)
613 word *c = T+m_modulus.reg.size();
614 word *f = T+2*m_modulus.reg.size();
615 word *g = T+3*m_modulus.reg.size();
616 size_t bcLen=1, fgLen=m_modulus.reg.size();
619 SetWords(T, 0, 3*m_modulus.reg.size());
621 assert(a.reg.size() <= m_modulus.reg.size());
622 CopyWords(f, a.reg, a.reg.size());
623 CopyWords(g, m_modulus.reg, m_modulus.reg.size());
630 ShiftWordsRightByWords(f, fgLen, 1);
633 assert(bcLen <= m_modulus.reg.size());
634 ShiftWordsLeftByWords(c, bcLen, 1);
647 if (t==1 && CountWords(f, fgLen)==1)
652 ShiftWordsRightByBits(f, fgLen, 1);
653 t=ShiftWordsLeftByBits(c, bcLen, 1);
657 ShiftWordsRightByBits(f, fgLen, i);
658 t=ShiftWordsLeftByBits(c, bcLen, i);
664 assert(bcLen <= m_modulus.reg.size());
667 if (f[fgLen-1]==0 && g[fgLen-1]==0)
670 if (f[fgLen-1] < g[fgLen-1])
676 XorWords(f, g, fgLen);
677 XorWords(b, c, bcLen);
680 while (k >= WORD_BITS)
691 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
692 temp ^= ((temp >> j) & 1) << (t1 + j);
694 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
697 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
701 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
702 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
705 b[t0/WORD_BITS-1] ^= temp;
712 word temp = b[0] << (WORD_BITS - k);
717 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
720 assert(t1+j < WORD_BITS);
721 temp ^= ((temp >> j) & 1) << (t1 + j);
726 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
730 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
734 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
735 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
738 b[t0/WORD_BITS-1] ^= temp;
741 CopyWords(result.reg.begin(), b, result.reg.size());
745 const GF2NT::Element& GF2NT::Multiply(
const Element &a,
const Element &b)
const 747 size_t aSize =
STDMIN(a.reg.
size(), result.reg.size());
748 Element r((word)0, m);
750 for (
int i=m-1; i>=0; i--)
754 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
755 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
758 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
761 XorWords(r.reg.begin(), a.reg, aSize);
765 r.reg.begin()[r.reg.size()-1] = (word)
Crop(r.reg[r.reg.size()-1], m%WORD_BITS);
767 CopyWords(result.reg.begin(), r.reg.begin(), result.reg.size());
771 const GF2NT::Element& GF2NT::Reduced(
const Element &a)
const 773 if (t0-t1 < WORD_BITS)
774 return m_domain.Mod(a, m_modulus);
785 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
786 b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
789 b[i-t0/WORD_BITS] ^= temp;
791 if ((t0-t1)%WORD_BITS)
793 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
794 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
797 b[i-(t0-t1)/WORD_BITS] ^= temp;
802 word mask = ((word)1<<(t0%WORD_BITS))-1;
803 word temp = b[i] & ~mask;
806 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
808 if ((t0-t1)%WORD_BITS)
810 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
811 if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
812 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
814 assert(temp << (WORD_BITS - (t0-t1)%WORD_BITS) == 0);
817 b[i-(t0-t1)/WORD_BITS] ^= temp;
820 SetWords(result.reg.begin(), 0, result.reg.size());
821 CopyWords(result.reg.begin(), b,
STDMIN(b.
size(), result.reg.size()));
827 a.DEREncodeAsOctetString(out, MaxElementByteLength());
832 a.BERDecodeAsOctetString(in, MaxElementByteLength());
838 ASN1::characteristic_two_field().DEREncode(seq);
841 ASN1::tpBasis().DEREncode(parameters);
843 parameters.MessageEnd();
850 ASN1::characteristic_two_field().DEREncode(seq);
853 ASN1::ppBasis().DEREncode(parameters);
858 pentanomial.MessageEnd();
859 parameters.MessageEnd();
868 if (
OID(seq) != ASN1::characteristic_two_field())
874 if (oid == ASN1::tpBasis())
878 result.reset(
new GF2NT(m, t1, 0));
880 else if (oid == ASN1::ppBasis())
882 unsigned int t1, t2, t3;
887 pentanomial.MessageEnd();
888 result.reset(
new GF2NPP(m, t3, t2, t1, 0));
895 parameters.MessageEnd();
898 return result.release();
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
Utility functions for the Crypto++ library.
PolynomialMod2()
creates the zero polynomial
Restricts the instantiation of a class to one static object without locks.
void CleanNew(size_type newSize)
Change size without preserving contents.
Class file for Randomness Pool.
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode unsigned value.
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
bool IsUnit() const
only 1 is a unit
GF(2^n) with Trinomial Basis.
size_t BitsToWords(size_t bitCount)
Returns the number of words required for the specified number of bits.
unsigned int BytePrecision(const T &value)
Returns the number of 8-bit bytes or octets required for a value.
void CleanGrow(size_type newSize)
Change size and preserve contents.
Secure memory block with allocator and cleanup.
Abstract base classes that provide a uniform interface to this library.
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
ASN.1 object identifiers for algorthms and schemes.
Classes for automatic resource management.
Library configuration file.
Interface for random number generators.
size_t BytesToWords(size_t byteCount)
Returns the number of words required for the specified number of bytes.
static PolynomialMod2 Monomial(size_t i)
return x^i
Classes for performing mathematics over different fields.
bool IsIrreducible() const
check for irreducibility
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
Polynomial with Coefficients in GF(2)
unsigned int BitCount() const
number of significant bits = Degree() + 1
static PolynomialMod2 Gcd(const PolynomialMod2 &a, const PolynomialMod2 &n)
greatest common divisor
Copy input to a memory buffer.
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
unsigned int Parity(T value)
Returns the parity of a value.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
String-based implementation of Store interface.
void SetByte(size_t n, byte value)
set the n-th byte to value
void BERDecodeError()
Raises a BERDecodeErr.
void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag=INTEGER, T minValue=0, T maxValue=((std::numeric_limits< T >::max)()))
BER Decode unsigned value.
Classes and functions for working with ANS.1 objects.
Implementation of BufferedTransformation's attachment interface.
GF(2^n) with Pentanomial Basis.
static PolynomialMod2 AllOnes(size_t n)
return x^(n-1) + ... + x + 1
GF(2^n) with Polynomial Basis.
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
PolynomialMod2 MultiplicativeInverse() const
return inverse if *this is a unit, otherwise return 0
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
static void Divide(PolynomialMod2 &r, PolynomialMod2 &q, const PolynomialMod2 &a, const PolynomialMod2 &d)
calculate r and q such that (a == d*q + r) && (deg(r) < deg(d))
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
byte GetByte(size_t n) const
return the n-th byte
signed int Degree() const
the zero polynomial will return a degree of -1
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
Crypto++ library namespace.
const Element & MultiplicativeInverse(const Element &a) const
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
return x^t0 + x^t1 + x^t2
unsigned int Parity() const
sum modulo 2 of all coefficients
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
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
size_type size() const
Provides the count of elements in the SecBlock.
#define SIZE_MAX
The maximum value of a machine word.