1 // gf2_32.cpp - originally written and placed in the public domain by Wei Dai 2 3 #include "pch.h" 4 #include "misc.h" 5 #include "gf2_32.h" 6 NAMESPACE_BEGIN(CryptoPP)7NAMESPACE_BEGIN(CryptoPP) 8 9 GF2_32::Element GF2_32::Multiply(Element a, Element b) const 10 { 11 word32 table[4]; 12 table[0] = 0; 13 table[1] = m_modulus; 14 if (a & 0x80000000) 15 { 16 table[2] = m_modulus ^ (a<<1); 17 table[3] = a<<1; 18 } 19 else 20 { 21 table[2] = a<<1; 22 table[3] = m_modulus ^ (a<<1); 23 } 24 25 #if CRYPTOPP_FAST_ROTATE(32) 26 b = rotrConstant<30>(b); 27 word32 result = table[b&2]; 28 29 for (int i=29; i>=0; --i) 30 { 31 b = rotlConstant<1>(b); 32 result = (result<<1) ^ table[(b&2) + (result>>31)]; 33 } 34 35 return (b&1) ? result ^ a : result; 36 #else 37 word32 result = table[(b>>30) & 2]; 38 39 for (int i=29; i>=0; --i) 40 result = (result<<1) ^ table[((b>>i)&2) + (result>>31)]; 41 42 return (b&1) ? result ^ a : result; 43 #endif 44 } 45 MultiplicativeInverse(Element a) const46GF2_32::Element GF2_32::MultiplicativeInverse(Element a) const 47 { 48 if (a <= 1) // 1 is a special case 49 return a; 50 51 // warning - don't try to adapt this algorithm for another situation 52 word32 g0=m_modulus, g1=a, g2=a; 53 word32 v0=0, v1=1, v2=1; 54 55 CRYPTOPP_ASSERT(g1); 56 57 while (!(g2 & 0x80000000)) 58 { 59 g2 <<= 1; 60 v2 <<= 1; 61 } 62 63 g2 <<= 1; 64 v2 <<= 1; 65 66 g0 ^= g2; 67 v0 ^= v2; 68 69 while (g0 != 1) 70 { 71 if (g1 < g0 || ((g0^g1) < g0 && (g0^g1) < g1)) 72 { 73 CRYPTOPP_ASSERT(BitPrecision(g1) <= BitPrecision(g0)); 74 g2 = g1; 75 v2 = v1; 76 } 77 else 78 { 79 CRYPTOPP_ASSERT(BitPrecision(g1) > BitPrecision(g0)); 80 g2 = g0; g0 = g1; g1 = g2; 81 v2 = v0; v0 = v1; v1 = v2; 82 } 83 84 while ((g0^g2) >= g2) 85 { 86 CRYPTOPP_ASSERT(BitPrecision(g0) > BitPrecision(g2)); 87 g2 <<= 1; 88 v2 <<= 1; 89 } 90 91 CRYPTOPP_ASSERT(BitPrecision(g0) == BitPrecision(g2)); 92 g0 ^= g2; 93 v0 ^= v2; 94 } 95 96 return v0; 97 } 98 99 NAMESPACE_END 100