Вычислить модуль числа в степени Certan (число в этой степени довольно большое)

Question

Я хочу самостоятельно рассчитать алгоритм RSA. Мне нужно рассчитать модуль числа при определенной степени. Дело в том, что это число при определенной мощности может стать довольно большим.

Вот что я хочу:

x = pow(n, p) % q

Как я могу эффективно определить х?

Answer 1

Это называется функцией powermod :

function modular_pow(base, exponent, modulus)
    c := 1
    for e_prime = 1 to exponent 
        c := (c * base) mod modulus
    return c

Это можно сделать более эффективным, применив возведение в степень путем возведения в квадрат:

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent & 1) equals 1:
           result = (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

Answer 2

Если вы используете .NET 4, я предлагаю вам взглянуть на BigInteger, который даже предоставляет метод ModPow для выполнения всего этого за одну операцию: )

BigInteger n = ...;
BigInteger p = ...;
BigInteger q = ...;
BigInteger x = BigInteger.ModPow(n, p, q);

Answer 3

Пожалуйста, отметьте эту тему и статью о том, как сделать математическую функцию более эффективной сама по себе.

Answer 4

См. BigInteger.ModPow (Fx 4+), вот это MSDN .

Answer 5

Тривиально ...

x = 1
for(i = 0; i < p; i++)
   x = (x*n) % q

Существуют более эффективные способы, такие как двоичное возведение в степень, а не эта наивная итерация, но это позволяет преодолеть проблему переполнения, так как x ограничен n * q

Answer 6

Хотя все ответы, представленные здесь, являются правильными, я пропускаю очевидный алгоритм вычисления квадрата и умножения, который является «классическим» способом реализации возведения в модуляр.

Answer 7

Если вы планируете написать свою собственную версию Modpow():

---

Вам нужна только мощность по модулю q, поэтому в ваших вычислениях не нужно использовать любое число больше q^2,используя тот факт, что:

if a = b (mod q) then a*p = b*p (mod q)

Поэтому при расчете мощности n^p после каждого умножения выполняйте (по модулю q) операцию с вашей рабочей переменной.

---

Кроме того, если q простое, вы можете использовать небольшую теорему Ферма, которая гласит:

a^(q-1) = 1 (mod q)
    (when a is not a multiple of q)

Это может быть использовано для сокращения вычислений, когда p равно (намного) больше чем q