Модульная экспонента в C

Question

Помощь! Мне нужно реализовать программу на C (используя только библиотеки строк, stdlib и stdio), которые используют модульное возведение в степень действительно больших чисел, некоторые из них - 260 цифр. Я думаю об использовании связанного списка, но я не могу найти хорошую ссылку о том, как его реализовать. Мне нужно это, потому что мне нужно использовать RSA для шифрования и расшифровки сообщения.

Кроме того, у меня есть такая же проблема при получении GCD двух очень больших чисел. Есть ли способ сделать это?

Answer 1

How to store large numbers? Вы можете использовать этот тип хранения ведьму данных один поможет вам использовать небольшое количество памяти и операции будут намного быстрее, чем все остальное, потому что вы можете сделать их directley на битах и ​​вы ч использовать специальные формулы : Для добавления Irecomand вы должны проверить переполнение;

умножения (х = х * у):

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 
}