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

(p-c^q) mod n

проблема в том что c и q очень большие (порядка 10 знаков), а p маленькое (пару цифр).
Пока посчитается выражение  (p-c^q)  проходит много времени...
потом быстренько mod выполняеться и все ок.

чувствую что как то можно ускорить это вычисление - убрав вычитание из скобок, т.е сведя это просто к (x^y) mod n
но незнаю как сделать. кто что может подсказать по этому поводу?

(p-c^q) mod n = (p-(c  mod n)^(q mod n)) mod n

Можно также ускорить за счет бинарного разложения (q mod n) и подсчета ((с mod n)^(2^k)) mod n

Добавлено через 1 минуту и 37 секунд

(a - b) mod n = ((a mod n) - (b mod n)) mod n
только что тебе это даст? 

не совсем
(c^q) mod n != (c^(q mod n)) mod n
пример:
(2^5) mod 3 = 32 mod 3 = 2
(2^(5 mod 3)) mod 3 = (2^2) mod 3 = 4 mod 3 = 1

если память меня не подводит, то в случае простого модуля можно брать показатель по модулю (n-1)
(или даже, когда НОД(c,n)=1)

http://en.wikipedia.org/wiki/Square-and-multiply_algorithm

maxim1000, да, тут чего-то меня не туда занесло... в ночи плохо соображается.

Есть чуйка такая что выражение a^b mod n
при больших a и b считается на порядок эффективнее чем (p-a^b) mod n
т.к не нужно целиком сначала вычислять выражение в скобках...за счет того и экономия..
но могу ошибаться.... не углублялся.. ))

Заменил по формуле
(a - b) mod n = ((a mod n) - (b mod n)) mod n
Собственно как и думал вычисляется теперь все очень быстро)

пишу на java - там даже ф-я специфичная есть BigInteger.modPow - возводит в степень и вычисляет mod
но это будет намного быстрее чем вычислять просто степень, при огромных числах.
т.к a*a*a*...*a mod n = ((((a mod n)*a ) mod n)*a mod n)... т.е мы не даем разростись результату постоянно уменьшая
его на каждом шаге операцией mod, это позволяет избежать возведения в огромную степень всего числа.

Это все очень не эффективно))))
Модуль разности равен разности модулей - это правильно...
Но вот возведение в степень по модулю можно сделать очень быстро...
Алгоритм примерно следующий..

возводит а в степень б по модулю...
типы не важны..сделаешь для себя какой нужен..

int pow(int a, int b, int mod)
{
   int res=1;
    while (b)
    {
        if (b%2)
            res=(res*a)%mod;
        b/=2;
        a=a*a;
    }
    return res;
}

Вот и все..считает очень быстро...
Может это неправильный алгоритм, но идея такая))
Просто система возведения в степень - это произведение чисел, являющихся а возведенными в степени двойки...
Скорость работы - логарифм числа б....
Позволяет возводить в очень большие степени...)))

AndreySUrSU,