Modular exponentation in C

Question

Help! I need to implement a C program (using only string, stdlib, and stdio libraries) which use modular exponentiation of really big numbers, some of them is 260 digits. I'm thinking of using a linked list but I cannot find a good reference on how to implement it.I need this because I need to use RSA to encrypt and decrypt a message.

Also, I have the exact same problem in getting the GCD of two very large numbers. Is there any way I can do this?

Answer 1

How to store large numbers? You can use this type of storing data witch one helps you to use a small amount of memory and for operations will be much faster than anything else because you can make them directley on bits and you ca use the special formulas : For add Irecomand you to check the overflow ;

multiply (x=x*y):

aux=x;x=0;
while(y)
{ 
  if(last_bit(y)==1)
     x=x+aux;
  shift_left(aux);
  shift_right(y);
}

function modular_pow(base, exponent, modulus)
{
if modulus = 1 then return 0
Assert :: (modulus - 1) * (modulus - 1) does not overflow base
result = 1
base = base mod modulus
while exponent > 0
    if (last_bit(exponent)==1):
       result = (result * base) mod modulus
    exponent = exponent >> 1
    base = (base * base) mod modulus
return result
}