Наименее неотрицательный остаток: Большие номера

Question

Я пытаюсь создать программу на C++, который может решить модульную конгруэнтность:

п^р = х (по модулю д),

где п - небольшое число, а р и q - очень большие произвольные простые числа. Я пытался сделать это несколько раз, но я всегда сталкивался с проблемами переполнения памяти. Любая помощь приветствуется.

Answer 1

Существует простой алгоритм б^е (мод м):

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 

Вы должны не вычислить б^е, а затем выполнить операцию по модулю , так как промежуточное число будет огромным. Я оставлю это вам, чтобы перевести на предпочтительный язык с типами данных, подходящими для хранения больших чисел, которые вам нужны. Я обсуждаю этот алгоритм на my blog.

Answer 2

Рассматривая ваши комментарии по вашему вопросу, кажется, что вы пытаетесь перебросить очень большие значения в переменные, которые не могут содержать большие значения.

Посмотрите здесь для получения дополнительной информации о типах данных и диапазонах они могут держать:
http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.110).aspx

Самый большой диапазон типов данных я нашел с неотрицательными числами unsigned long long. Он содержит диапазон значений от 0 до 18 446 744 073 709 551 615.