Crypto++  5.6.5 Free C++ class library of cryptographic schemes
gf2_32.cpp
1 // gf2_32.cpp - 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
7 NAMESPACE_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 = rotrFixed(b, 30U);
27  word32 result = table[b&2];
28
29  for (int i=29; i>=0; --i)
30  {
31  b = rotlFixed(b, 1U);
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
46 GF2_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  {
74  g2 = g1;
75  v2 = v1;
76  }
77  else
78  {
80  g2 = g0; g0 = g1; g1 = g2;
81  v2 = v0; v0 = v1; v1 = v2;
82  }
83
84  while ((g0^g2) >= g2)
85  {
87  g2 <<= 1;
88  v2 <<= 1;
89  }
90
92  g0 ^= g2;
93  v0 ^= v2;
94  }
95
96  return v0;
97 }
98
99 NAMESPACE_END
GF(2^32) with polynomial basis.
Definition: gf2_32.h:16
Utility functions for the Crypto++ library.
T rotlFixed(T x, unsigned int y)
Performs a left rotate.
Definition: misc.h:1263
Classes and functions for schemes over GF(2^32)
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:62
Crypto++ library namespace.
T rotrFixed(T x, unsigned int y)
Performs a right rotate.
Definition: misc.h:1285
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:654