6 #ifndef CRYPTOPP_IMPORTS
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++)
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);
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;
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;
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++)
589 }
while (w.IsZero());
598 GF2NT::GF2NT(
unsigned int c0,
unsigned int c1,
unsigned int c2)
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());
622 CopyWords(f, a.reg, a.reg.size());
623 CopyWords(g, m_modulus.reg, m_modulus.reg.size());
630 ShiftWordsRightByWords(f, fgLen, 1);
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);
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)
689 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
693 const unsigned int shift = t1 + j;
695 temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
698 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
701 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
705 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
706 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
709 b[t0/WORD_BITS-1] ^= temp;
716 word temp = b[0] << (WORD_BITS - k);
721 for (
unsigned int j=0; j<WORD_BITS-t1; j++)
725 const unsigned int shift = t1 + j;
727 temp ^= (shift < WORD_BITS) ? (((temp >> j) & 1) << shift) : 0;
732 b[t1/WORD_BITS-1] ^= temp << t1%WORD_BITS;
736 b[t1/WORD_BITS] ^= temp >> (WORD_BITS - t1%WORD_BITS);
740 b[t0/WORD_BITS-1] ^= temp << t0%WORD_BITS;
741 b[t0/WORD_BITS] ^= temp >> (WORD_BITS - t0%WORD_BITS);
744 b[t0/WORD_BITS-1] ^= temp;
747 CopyWords(result.reg.
begin(), b, result.reg.
size());
753 size_t aSize =
STDMIN(a.reg.size(), result.reg.
size());
754 Element r((word)0, m);
756 for (
int i=m-1; i>=0; i--)
760 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
761 XorWords(r.reg.begin(), m_modulus.reg, r.reg.size());
764 ShiftWordsLeftByBits(r.reg.begin(), r.reg.size(), 1);
767 XorWords(r.reg.begin(), a.reg, aSize);
771 r.reg.begin()[r.reg.size()-1] = (word)
Crop(r.reg[r.reg.size()-1], m%WORD_BITS);
773 CopyWords(result.reg.
begin(), r.reg.begin(), result.reg.
size());
777 const GF2NT::Element& GF2NT::Reduced(
const Element &a)
const
779 if (t0-t1 < WORD_BITS)
780 return m_domain.Mod(a, m_modulus);
791 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
792 b[i-t0/WORD_BITS-1] ^= temp << (WORD_BITS - t0%WORD_BITS);
795 b[i-t0/WORD_BITS] ^= temp;
797 if ((t0-t1)%WORD_BITS)
799 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
800 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
803 b[i-(t0-t1)/WORD_BITS] ^= temp;
808 word mask = ((word)1<<(t0%WORD_BITS))-1;
809 word temp = b[i] & ~mask;
812 b[i-t0/WORD_BITS] ^= temp >> t0%WORD_BITS;
814 if ((t0-t1)%WORD_BITS)
816 b[i-(t0-t1)/WORD_BITS] ^= temp >> (t0-t1)%WORD_BITS;
817 if ((t0-t1)%WORD_BITS > t0%WORD_BITS)
818 b[i-(t0-t1)/WORD_BITS-1] ^= temp << (WORD_BITS - (t0-t1)%WORD_BITS);
823 b[i-(t0-t1)/WORD_BITS] ^= temp;
826 SetWords(result.reg.
begin(), 0, result.reg.
size());
833 a.DEREncodeAsOctetString(out, MaxElementByteLength());
838 a.BERDecodeAsOctetString(in, MaxElementByteLength());
844 ASN1::characteristic_two_field().DEREncode(seq);
847 ASN1::tpBasis().DEREncode(parameters);
849 parameters.MessageEnd();
856 ASN1::characteristic_two_field().DEREncode(seq);
859 ASN1::ppBasis().DEREncode(parameters);
864 pentanomial.MessageEnd();
865 parameters.MessageEnd();
874 if (
OID(seq) != ASN1::characteristic_two_field())
880 if (oid == ASN1::tpBasis())
884 result.reset(
new GF2NT(m, t1, 0));
886 else if (oid == ASN1::ppBasis())
888 unsigned int t1, t2, t3;
893 pentanomial.MessageEnd();
894 result.reset(
new GF2NPP(m, t3, t2, t1, 0));
901 parameters.MessageEnd();
904 return result.release();