gf2_32.cpp
// gf2_32.cpp - originally written and placed in the public domain by Wei Dai
#include "pch.h"
#include "misc.h"
#include "gf2_32.h"
NAMESPACE_BEGIN(CryptoPP)
GF2_32::Element GF2_32::Multiply(Element a, Element b) const
{
word32 table[4];
table[0] = 0;
table[1] = m_modulus;
if (a & 0x80000000)
{
table[2] = m_modulus ^ (a<<1);
table[3] = a<<1;
}
else
{
table[2] = a<<1;
table[3] = m_modulus ^ (a<<1);
}
#if CRYPTOPP_FAST_ROTATE(32)
b = rotrConstant<30>(b);
word32 result = table[b&2];
for (int i=29; i>=0; --i)
{
b = rotlConstant<1>(b);
result = (result<<1) ^ table[(b&2) + (result>>31)];
}
return (b&1) ? result ^ a : result;
#else
word32 result = table[(b>>30) & 2];
for (int i=29; i>=0; --i)
result = (result<<1) ^ table[((b>>i)&2) + (result>>31)];
return (b&1) ? result ^ a : result;
#endif
}
GF2_32::Element GF2_32::MultiplicativeInverse(Element a) const
{
if (a <= 1) // 1 is a special case
return a;
// warning - don't try to adapt this algorithm for another situation
word32 g0=m_modulus, g1=a, g2=a;
word32 v0=0, v1=1, v2=1;
CRYPTOPP_ASSERT(g1);
while (!(g2 & 0x80000000))
{
g2 <<= 1;
v2 <<= 1;
}
g2 <<= 1;
v2 <<= 1;
g0 ^= g2;
v0 ^= v2;
while (g0 != 1)
{
if (g1 < g0 || ((g0^g1) < g0 && (g0^g1) < g1))
{
CRYPTOPP_ASSERT(BitPrecision(g1) <= BitPrecision(g0));
g2 = g1;
v2 = v1;
}
else
{
CRYPTOPP_ASSERT(BitPrecision(g1) > BitPrecision(g0));
g2 = g0; g0 = g1; g1 = g2;
v2 = v0; v0 = v1; v1 = v2;
}
while ((g0^g2) >= g2)
{
CRYPTOPP_ASSERT(BitPrecision(g0) > BitPrecision(g2));
g2 <<= 1;
v2 <<= 1;
}
CRYPTOPP_ASSERT(BitPrecision(g0) == BitPrecision(g2));
g0 ^= g2;
v0 ^= v2;
}
return v0;
}
NAMESPACE_END
Element
word32
unsigned int word32
32-bit unsigned datatype
Definition config_int.h:72
gf2_32.h
Classes and functions for schemes over GF(2^32).
misc.h
Utility functions for the Crypto++ library.
rotlConstant
T rotlConstant(T x)
Performs a left rotate.
Definition misc.h:1757
BitPrecision
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition misc.h:1047
rotrConstant
T rotrConstant(T x)
Performs a right rotate.
Definition misc.h:1783
CryptoPP
Crypto++ library namespace.
pch.h
Precompiled header file.
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition trap.h:68