Модульное возведение в степень в C

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

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


encryption rsa exponentiation modular-arithmetic
person Xael Yvette    schedule 24.09.2016    source источник
comment
Я забыл упомянуть, что числа, которые я собираюсь сделать модульными, уже хранятся в отдельных цифрах в связанном списке.   -  person Xael Yvette    schedule 25.09.2016
comment
Вам понадобится реализация BigInteger на C. Если вы ограничены этими библиотеками, то это потребует много работы. Это домашнее задание? Вы уверены, что не можете реализовать это с меньшими числами?   -  person Luke Joshua Park    schedule 25.09.2016
comment
Да, это так. Ожидается, что мы будем иметь дело с числами, превышающими предел целых чисел. @ЛюкПарк   -  person Xael Yvette    schedule 25.09.2016
comment
Ну удачи с этим. Вам придется написать собственную реализацию BigInteger. Веселиться.   -  person Luke Joshua Park    schedule 25.09.2016

Ответы (1)


arrow_upward
2
arrow_downward

Как хранить большие числа? Вы можете использовать этот тип хранения данных, который поможет вам для использования небольшого объема памяти и для операций будет намного быстрее, чем что-либо еще, потому что вы можете сделать их прямо на биты и вы можете использовать специальные формулы: Для добавления 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
}
person Popovici Sebi    schedule 04.10.2016