| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > как ускорить такое вычисление? |
| Автор: 31416 16.4.2007, 22:44 |
| Реализую алгоритм шифрования рабина, приходиться вычислять такую штуку: (p-c^q) mod n проблема в том что c и q очень большие (порядка 10 знаков), а p маленькое (пару цифр). Пока посчитается выражение (p-c^q) проходит много времени... потом быстренько mod выполняеться и все ок. чувствую что как то можно ускорить это вычисление - убрав вычитание из скобок, т.е сведя это просто к (x^y) mod n но незнаю как сделать. кто что может подсказать по этому поводу? |
| Автор: Akina 16.4.2007, 22:50 | ||
| (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 только что тебе это даст? |
| Автор: maxim1000 16.4.2007, 23:32 | ||
не совсем (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) |
| Автор: sergejzr 16.4.2007, 23:57 |
| http://en.wikipedia.org/wiki/Square-and-multiply_algorithm |
| Автор: Akina 17.4.2007, 07:37 |
| maxim1000, да, тут чего-то меня не туда занесло... в ночи плохо соображается. |
| Автор: 31416 17.4.2007, 20:13 | ||
Есть чуйка такая что выражение a^b mod n при больших a и b считается на порядок эффективнее чем (p-a^b) mod n т.к не нужно целиком сначала вычислять выражение в скобках...за счет того и экономия.. но могу ошибаться.... не углублялся.. )) |
| Автор: 31416 18.4.2007, 17:23 |
| Заменил по формуле (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, это позволяет избежать возведения в огромную степень всего числа. |
| Автор: AndreySUrSU 22.4.2007, 16:06 |
| Это все очень не эффективно)))) Модуль разности равен разности модулей - это правильно... Но вот возведение в степень по модулю можно сделать очень быстро... Алгоритм примерно следующий.. возводит а в степень б по модулю... типы не важны..сделаешь для себя какой нужен.. 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; } Вот и все..считает очень быстро... Может это неправильный алгоритм, но идея такая)) Просто система возведения в степень - это произведение чисел, являющихся а возведенными в степени двойки... Скорость работы - логарифм числа б.... Позволяет возводить в очень большие степени...))) |
| Автор: sergejzr 22.4.2007, 20:04 | ||
AndreySUrSU,
|
