Modular exponentiation
Hello
Im trying to calculate a modular exponentiation using UInt.
Problem is that the power im using is really big. So something like
2^(100 digit number) % b
Is there any way to perform this calculation using ttmath?
Thanks in advance
Currently there is no any built-in function to do it, you have to write your own method. For example by using right-to-left binary algorithm it can be as follows:
// result = (base ^ exponent) mod modulus
template<typename Integer>
int powm(const Integer & base, const Integer & exponent,
const Integer & modulus, Integer & result)
{
int c = 0;
Integer rem, b, e;
if( (base == 0 && exponent == 0) || modulus == 0 )
return 1;
result = 1;
b = base;
e = exponent;
while( e > 0 )
{
if( e.IsTheLowestBitSet() )
{
c += result.Mul(b);
c += result.Div(modulus, &rem);
result = rem;
}
e.Rcr(1);
c += b.Mul(b);
c += b.Div(modulus, &rem);
b = rem;
}
return (c > 0) ? 1 : 0;
}
and can be used in this way:
int main()
{
typedef ttmath::UInt<30> MyInt;
MyInt a, b, c, res;
a = "2344";
b = "13134545645645645634534534534535434534531";
c = "42334";
int carry = powm(a, b, c, res); // res = (a^b) mod c
if( carry )
std::cout << "ops, the container MyInt is too small" << std::endl;
else
std::cout << res << std::endl;
}
Thank you very much for your answer. I will try that and i will let you know how it goes.
By the way, im using ttmath with iOS6. Works flawlessly. If anyone needs more info of how to do it, let me know
The implementation provided here works but it is ~100 times slower than its counterpart in standard Diffie-Hellman implementations. Generation of a public value + verification take ~400ms on a modern machine with a 2304bit modulus and 256bit exponents whereas DH implementations take ~4ms for the same operation.
I'd like to post a belated addition to that: It was taking 400ms on Debug builds, with Release it takes ~100ms which makes it much better, but it's still ~25 times slower than mature crypto implementations.