|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 24 Mar 2002 22:10:53
To : fat
Subject : Вычисление чисел по модулю
--------------------------------------------------------------------------------
24 Mar 02 19:14, you wrote to All:
f> Как вычислить (X^Y)mod(z) (читать как X в тепени Y по модулю z), не
f> прямым способом, т.е. (X^Y)mod(z) = (X^Y)-floor((X^Y)/z)??? :-)
Пусть двоичное представление числа x это
x = x{n-1}x{n-2}x{n-3}...x{1}x{0}
где x = SUM(x{i}*2^i,0,n-1)
Тогда алгоритм для вычисления a^x (mod q):
r = 1
for i=n-1 down to 0 do
r = r^2 * a^x{i} (mod q) // denote: a^x{i} is either 1 or a itself
После выполнения этого for получаем:
r = a^x (mod q)
Cложность алгоритма:
O(log x) в худшем случае, O(log q) в среднем.
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
