Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Кажется так, поправьтеесли ошибки... 24.03.04 14:10 Число просмотров: 3986
Автор: Xelator Статус: Незарегистрированный пользователь
|
От исходной задачи рассмотрим только вычисление x^(p-2)
Пусть (p-2) n-битное число.. представим его в виде суммы его бит: (p-2) = sum(i=0,n)(2^k[i]),
здесь k[i] = {0, i} зависит от того чему равен i-ый бит в числе (p-2).
Возьмем худший вариант - все n бит в (p-2) равны 1.
Тогда (сумму будем понимать в смыле цикла for языка C, т.е. n не включается):
x^(p-2) = x^(sum(i=0,n)(2^k[i])) = x^(2^k[0]) * x^(2^k[1]) * ... x^(2^k[n-1])
Выходит нам требуется следующие вычисления в худшем случае:
1) (n-1) приведение по модулю поля для каждого x^(2^k[i])
2) (n-1) умножения приведенных результатов x^(2^k[i])
3) посчитать все x^(2^k[i]) в том числе сделать для них приведения по модулю в процессе.
так-так пункт 3) требует - n^2 возведений в квадрат и приведений по модулю (если я правильно считаю арифмитическую прогрессию ;-))).
итого = n^2 + 2n - 2 = (n-1)^2 - 1 возведений в квадрат и приведений по модулю
Т.е. для 256-битного числа (хотя модульгый трехчлен вроде был 191 степени?) получается
65524 возведений в квадрат и приведений по модулю.
Выходит критическая масса сидит в умножениях - умножайте быстро!
Возведение в квадрат в бинарном поле это "раздвигание" бит по четным позициям.
Быстрое приведение на трехчлен (то же для пятичлена) обсуждалось выше.
|
|
|