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)
609 return GF2NP::MultiplicativeInverse(a);
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 IsIrreducible() const
check for irreducibility
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from → to is safe to perform.
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
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.
size_t DEREncodeUnsigned(BufferedTransformation &out, T w, byte asnTag=INTEGER)
DER Encode Unsigned.
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
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.
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
signed int Degree() const
the zero polynomial will return a degree of -1
size_type size() const
Provides the count of elements in the SecBlock.
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.
byte GetByte(size_t n) const
return the n-th byte
static PolynomialMod2 Monomial(size_t i)
return x^i
SecByteBlock is a SecBlock<byte> typedef.
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
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.
bool IsUnit() const
only 1 is a unit
T Crop(T value, size_t bits)
Truncates the value to the specified number of bits.
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
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
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
void BERDecodeUnsigned(BufferedTransformation &in, T &w, byte asnTag=INTEGER, T minValue=0, T maxValue=((std::numeric_limits< T >::max)()))
BER Decode Unsigned.
Classes and functions for working with ANS.1 objects.
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
Implementation of BufferedTransformation's attachment interface in cryptlib.h.
GF(2^n) with Pentanomial Basis.
static PolynomialMod2 AllOnes(size_t n)
return x^(n-1) + ... + x + 1
GF(2^n) with Polynomial Basis.
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))
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
Crypto++ library namespace.
unsigned int Parity() const
sum modulo 2 of all coefficients
static PolynomialMod2 Trinomial(size_t t0, size_t t1, size_t t2)
return x^t0 + x^t1 + x^t2
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.
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
#define SIZE_MAX
The maximum value of a machine word.