5 #ifndef CRYPTOPP_IMPORTS
16 NAMESPACE_BEGIN(CryptoPP)
23 : reg(BitsToWords(bitLength))
25 assert(value==0 || reg.size()>0);
30 SetWords(reg+1, 0, reg.size()-1);
37 CopyWords(reg, t.reg, reg.size());
42 const size_t nbytes = nbits/8 + 1;
45 buf[0] = (byte)Crop(buf[0], nbits % 8);
52 SetWords(result.reg, ~(word)0, result.reg.size());
53 if (bitLength%WORD_BITS)
54 result.reg[result.reg.size()-1] = (word)Crop(result.reg[result.reg.size()-1], bitLength%WORD_BITS);
58 void PolynomialMod2::SetBit(
size_t n,
int value)
63 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
67 if (n/WORD_BITS < reg.size())
68 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
74 if (n/WORD_SIZE >= reg.size())
77 return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
83 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
84 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
133 void PolynomialMod2::Decode(
const byte *input,
size_t inputLen)
136 Decode(store, inputLen);
147 reg.
CleanNew(BytesToWords(inputLen));
149 for (
size_t i=inputLen; i > 0; i--)
153 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
159 for (
size_t i=outputLen; i > 0; i--)
173 if (!dec.IsDefiniteLength() || dec.RemainingLength() != length)
181 return (
unsigned int)CountWords(reg, reg.size());
188 return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]);
197 return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]);
206 for (i=0; i<reg.size(); i++)
208 return CryptoPP::Parity(temp);
220 XorWords(reg, t.reg, t.reg.size());
226 if (b.reg.size() >= reg.size())
229 XorWords(result.reg, reg, b.reg, reg.size());
230 CopyWords(result.reg+reg.size(), b.reg+reg.size(), b.reg.size()-reg.size());
236 XorWords(result.reg, reg, b.reg, b.reg.size());
237 CopyWords(result.reg+b.reg.size(), reg+b.reg.size(), reg.size()-b.reg.size());
244 PolynomialMod2 result((word)0, WORD_BITS*STDMIN(reg.size(), b.reg.size()));
245 AndWords(result.reg, reg, b.reg, result.reg.size());
253 for (
int i=b.
Degree(); i>=0; i--)
257 XorWords(result.reg, reg, reg.size());
264 static const word map[16] = {0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85};
268 for (
unsigned i=0; i<reg.size(); i++)
272 for (j=0; j<WORD_BITS; j+=8)
273 result.reg[2*i] |= map[(reg[i] >> (j/2)) % 16] << j;
275 for (j=0; j<WORD_BITS; j+=8)
276 result.reg[2*i+1] |= map[(reg[i] >> (j/2 + WORD_BITS/2)) % 16] << j;
288 int degree = divisor.
Degree();
289 remainder.reg.
CleanNew(BitsToWords(degree+1));
295 for (
int i=dividend.
Degree(); i>=0; i--)
298 remainder.reg[0] |= dividend[i];
299 if (remainder[degree])
301 remainder -= divisor;
337 *r = (u << 1) | carry;
338 carry = u >> (WORD_BITS-1);
344 reg.
Grow(reg.size()+1);
345 reg[reg.size()-1] = carry;
351 int shiftWords = n / WORD_BITS;
352 int shiftBits = n % WORD_BITS;
360 *r = (u << shiftBits) | carry;
361 carry = u >> (WORD_BITS-shiftBits);
368 reg.
Grow(reg.size()+shiftWords+1);
369 reg[reg.size()-1] = carry;
372 reg.
Grow(reg.size()+shiftWords);
376 for (i = (
int)reg.size()-1; i>=shiftWords; i--)
377 reg[i] = reg[i-shiftWords];
390 int shiftWords = n / WORD_BITS;
391 int shiftBits = n % WORD_BITS;
396 word *r=reg+reg.size()-1;
404 *r = (u >> shiftBits) | carry;
405 carry = u << (WORD_BITS-shiftBits);
412 for (i=0; i<reg.size()-shiftWords; i++)
413 reg[i] = reg[i+shiftWords];
414 for (; i<reg.size(); i++)
433 bool PolynomialMod2::operator!()
const
435 for (
unsigned i=0; i<reg.size(); i++)
436 if (reg[i])
return false;
442 size_t i, smallerSize = STDMIN(reg.size(), rhs.reg.size());
444 for (i=0; i<smallerSize; i++)
445 if (reg[i] != rhs.reg[i])
return false;
447 for (i=smallerSize; i<reg.size(); i++)
448 if (reg[i] != 0)
return false;
450 for (i=smallerSize; i<rhs.reg.size(); i++)
451 if (rhs.reg[i] != 0)
return false;
456 std::ostream& operator<<(std::ostream& out,
const PolynomialMod2 &a)
459 long f = out.flags() & std::ios::basefield;
481 return out <<
'0' << suffix;
486 static const char upper[]=
"0123456789ABCDEF";
487 static const char lower[]=
"0123456789abcdef";
488 const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower;
490 for (i=0; i*bits < a.
BitCount(); i++)
493 for (
int j=0; j<bits; j++)
494 digit |= a[i*bits+j] << j;
501 if (i && (i%block)==0)
505 return out << suffix;
526 for (
int i=1; i<=d/2; i++)
528 u = u.Squared()%(*this);
542 GF2NP::Element GF2NP::SquareRoot(
const Element &a)
const
545 for (
unsigned int i=1; i<m; i++)
550 GF2NP::Element GF2NP::HalfTrace(
const Element &a)
const
554 for (
unsigned int i=1; i<=(m-1)/2; i++)
559 GF2NP::Element GF2NP::SolveQuadraticEquation(
const Element &a)
const
568 z = PolynomialMod2::Zero();
570 for (
unsigned int i=1; i<=m-1; i++)
574 Accumulate(z, Multiply(w, a));
577 }
while (w.IsZero());
586 GF2NT::GF2NT(
unsigned int t0,
unsigned int t1,
unsigned int t2)
591 assert(t0 > t1 && t1 > t2 && t2==0);
594 const GF2NT::Element& GF2NT::MultiplicativeInverse(
const Element &a)
const
596 if (t0-t1 < WORD_BITS)
597 return GF2NP::MultiplicativeInverse(a);
601 word *c = T+m_modulus.reg.size();
602 word *f = T+2*m_modulus.reg.size();
603 word *g = T+3*m_modulus.reg.size();
604 size_t bcLen=1, fgLen=m_modulus.reg.size();
607 SetWords(T, 0, 3*m_modulus.reg.size());
609 assert(a.reg.size() <= m_modulus.reg.size());
610 CopyWords(f, a.reg, a.reg.size());
611 CopyWords(g, m_modulus.reg, m_modulus.reg.size());
618 ShiftWordsRightByWords(f, fgLen, 1);
621 assert(bcLen <= m_modulus.reg.size());
622 ShiftWordsLeftByWords(c, bcLen, 1);
635 if (t==1 && CountWords(f, fgLen)==1)
640 ShiftWordsRightByBits(f, fgLen, 1);
641 t=ShiftWordsLeftByBits(c, bcLen, 1);
645 ShiftWordsRightByBits(f, fgLen, i);
646 t=ShiftWordsLeftByBits(c, bcLen, i);
652 assert(bcLen <= m_modulus.reg.size());
655 if (f[fgLen-1]==0 && g[fgLen-1]==0)
658 if (f[fgLen-1] < g[fgLen-1])
664 XorWords(f, g, fgLen);
665 XorWords(b, c, bcLen);
668 while (k >= WORD_BITS)
672 for (
unsigned i=0; i+1<BitsToWords(m); i++)
674 b[BitsToWords(m)-1] = 0;
677 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
678 temp ^= ((temp >> j) & 1) << (t1 + j);
680 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
683 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
687 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
688 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
691 b[t0/WORD_BITS-1] ^= temp;
698 word temp = b[0] << (WORD_BITS - k);
699 ShiftWordsRightByBits(b, BitsToWords(m), k);
702 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
703 temp ^= ((temp >> j) & 1) << (t1 + j);
705 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
708 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
712 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
713 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
716 b[t0/WORD_BITS-1] ^= temp;
719 CopyWords(result.reg.begin(), b, result.reg.size());
723 const GF2NT::Element& GF2NT::Multiply(
const Element &a,
const Element &b)
const
725 size_t aSize = STDMIN(a.reg.size(), result.reg.size());
726 Element r((word)0, m);
728 for (
int i=m-1; i>=0; i--)
732 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
733 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
736 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
739 XorWords(r.reg.begin(), a.reg, aSize);
743 r.reg.begin()[r.reg.size()-1] = (word)Crop(r.reg[r.reg.size()-1], m%WORD_BITS);
745 CopyWords(result.reg.begin(), r.reg.begin(), result.reg.size());
749 const GF2NT::Element& GF2NT::Reduced(
const Element &a)
const
751 if (t0-t1 < WORD_BITS)
752 return m_domain.Mod(a, m_modulus);
757 for (i=b.size()-1; i>=BitsToWords(t0); i--)
763 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
764 b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
767 b[i-t0/WORD_BITS] ^= temp;
769 if ((t0-t1)%WORD_BITS)
771 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
772 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
775 b[i-(t0-t1)/WORD_BITS] ^= temp;
778 if (i==BitsToWords(t0)-1 && t0%WORD_BITS)
780 word mask = ((word)1<<(t0%WORD_BITS))-1;
781 word temp = b[i] & ~mask;
784 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
786 if ((t0-t1)%WORD_BITS)
788 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
789 if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
790 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
792 assert(temp << (WORD_BITS - (t0-t1)%WORD_BITS) == 0);
795 b[i-(t0-t1)/WORD_BITS] ^= temp;
798 SetWords(result.reg.begin(), 0, result.reg.size());
799 CopyWords(result.reg.begin(), b, STDMIN(b.size(), result.reg.size()));
805 a.DEREncodeAsOctetString(out, MaxElementByteLength());
810 a.BERDecodeAsOctetString(in, MaxElementByteLength());
816 ASN1::characteristic_two_field().DEREncode(seq);
818 DEREncodeUnsigned(parameters, m);
819 ASN1::tpBasis().DEREncode(parameters);
820 DEREncodeUnsigned(parameters, t1);
821 parameters.MessageEnd();
828 ASN1::characteristic_two_field().DEREncode(seq);
830 DEREncodeUnsigned(parameters, m);
831 ASN1::ppBasis().DEREncode(parameters);
833 DEREncodeUnsigned(pentanomial, t3);
834 DEREncodeUnsigned(pentanomial, t2);
835 DEREncodeUnsigned(pentanomial, t1);
836 pentanomial.MessageEnd();
837 parameters.MessageEnd();
847 if (
OID(seq) != ASN1::characteristic_two_field())
851 BERDecodeUnsigned(parameters, m);
853 if (oid == ASN1::tpBasis())
856 BERDecodeUnsigned(parameters, t1);
857 result.reset(
new GF2NT(m, t1, 0));
859 else if (oid == ASN1::ppBasis())
861 unsigned int t1, t2, t3;
863 BERDecodeUnsigned(pentanomial, t3);
864 BERDecodeUnsigned(pentanomial, t2);
865 BERDecodeUnsigned(pentanomial, t1);
866 pentanomial.MessageEnd();
867 result.reset(
new GF2NPP(m, t3, t2, t1, 0));
874 parameters.MessageEnd();
877 return result.release();
bool IsIrreducible() const
check for irreducibility
void DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const
encode value as big-endian octet string
PolynomialMod2()
creates the zero polynomial
void CleanNew(size_type newSize)
change size and set contents to 0
virtual void GenerateBlock(byte *output, size_t size)
generate random array of bytes
GF(2^n) with Trinomial Basis.
void CleanGrow(size_type newSize)
change size only if newSize > current size. contents are preserved and additional area is set to 0 ...
a block of memory allocated using A
unsigned int ByteCount() const
number of significant bytes = ceiling(BitCount()/8)
signed int Degree() const
the zero polynomial will return a degree of -1
interface for random number generators
byte GetByte(size_t n) const
return the n-th byte
static PolynomialMod2 Monomial(size_t i)
return x^i
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
void Encode(byte *output, size_t outputLen) const
encode in big-endian format
void Assign(const T *t, size_type len)
set contents and size
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))
PolynomialMod2 InverseMod(const PolynomialMod2 &) const
calculate multiplicative inverse of *this mod n
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 Grow(size_type newSize)
change size only if newSize > current size. contents are preserved
void BERDecodeAsOctetString(BufferedTransformation &bt, size_t length)
decode value as big-endian octet string
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