Наименее неотрицательный остаток: большие числа
Я пытаюсь создать программу C ++, которая может решить модульную конгруэнтность:
n ^ p = x (mod q),
где n — небольшое число, а p и q — очень большие произвольные простые числа. Я пытался сделать это несколько раз, но я всегда сталкиваюсь с проблемами переполнения памяти. Любая помощь приветствуется.
Решение
Существует простой алгоритм для б ^ е (моды м):
function powerMod(b, e, m)
x := 1
while e > 0
if e % 2 == 1
x := (b * x) % m
b := (b * b) % m
e := e // 2 # integer division
return x
Вам следует не подсчитывать б ^ е и затем выполните операцию по модулю, так как промежуточное число будет огромным. Я оставлю вам перевод на ваш предпочитаемый язык с типами данных, подходящими для хранения большого количества нужных вам чисел. Я обсуждаю этот алгоритм на мой блог.
Другие решения
Глядя на ваши комментарии к вашему вопросу, кажется, что вы пытаетесь засунуть очень большие значения в переменные, которые не могут содержать такие большие значения.
Посмотрите здесь для получения дополнительной информации о типах данных и диапазонах, которые они могут содержать:
http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.110).aspx
Самый большой диапазон типов данных, который я нашел с неотрицательными числами, unsigned long long, Он содержит диапазон значений от 0 до 18,446,744,073,709,551,615.