Возведение в степень по модулю (можно ли ускорить для осн.2)

[ubik77]

Ales в сообщении #808684 писал(а):

ubik77 в сообщении #808674 писал(а):

Возможно именно для двойки его можно как-то оптимизировать.

Думаю, что нельзя.
2 нужно возводить в квадрат.
Уже на 10-м шаге выходим на $2^{1024}$, вылезаем за модуль и получаем обычное число.

Для кольца вычетов по модулю нечетного простого числа 2, как элемент кольца,
должно быть ничем не лучше и не хуже других чисел.

Зато 2-ка имеет особые свойства для операций с элементами кольца,
ведь 2-ка делит число ненулевых вычетов.

Найти у 2-ки какие-то особые свойства, как элемента кольца - сверхдостижение,
возможно взламывающее загадку дискретного логарифма.

Да, похоже так. Ну тогда в реализации алгоритма как-то поплясать, чтобы ускорить его работу. Хотя бы раза в 4. Как минимум вместо умножения в случае основания 2 можно просто число сдвигать на бит. Или не сдвигать, чтобы сэкономить на операциях копирования, а просто указатель/счётчик перемещать или что-то подобное. Возведение в квадрат по модулю как-то оптимизировать и т.п.

-- 02.01.2014, 17:56 --

Ales в сообщении #808684 писал(а):

Поэтому операции с любым вычетом не хуже и не лучше, чем операции с 2.

Я ещё думал, что можно зайти с обратной стороны. При проверке последний шаг y*y mod N, и результат должен быть равен 1. Я думал, можно ли проверить, является ли квадратом (N*k+1), где k можен принимать любые целые значения от 0 и больше. Но оказалось что это проверить нельзя.

[venco]

Самое медленное в возведении в степень по большому модулю - вычисление остатка от деления. В gmp для ускорения этой операции используют Montgomery reduction, т.к. в случае многократного деления накладные расходы становятся незначительны. А в представлении Монтгомери двойка уже не является особенно выгодным числом. Так что в gmp уже всё сделали оптимально.
Про это уже говорил Xaositect на первой странице, но вы, похоже, не заметили или не поняли.

[ubik77]

venco в сообщении #808708 писал(а):

Самое медленное в возведении в степень по большому модулю - вычисление остатка от деления. В gmp для ускорения этой операции используют Montgomery reduction, т.к. в случае многократного деления накладные расходы становятся незначительны.

А что, разве метод Монтгомери можно использовать и в делении? Я думал только в умножении по модулю, причём там нужно делать преобразования для каждого нового числа. Алгоритм же всё-равно пошаговый и на каждом шаге остатки новые. Просто я где-то читал, что Монтгомери даже в два раза не даёт ускорение по сравнению с квадратами. Возможно ошибаюсь.

Ещё нашел статью: http://is.gd/AsBtiD (PDF)
Но не могу оценить её полезность, потому что не понял. Пишут, что:

"Достигаемая за счет этого оптимизация синтезированных мультипликативных алгоритмов обеспечивает (3,5−3,6)-кратное повышение производительности (в сравнении с наиболее близким модулярным аналогом) при выполнении на однопроцессорной ЭВМ."

С чем они сравнивают - не понятно.

[venco]

Метод Монтгомери применяют именно для умножения по модулю. Без него пришлось бы просто брать модуль (делить). У метода Монтгомери есть большие накладные расходы, поэтому для однократного умножения по модулю он не выгоден. Но если эту операцию надо выполнить много раз с одним и тем же модулем, как это делается при возведении в степень, то потери становятся незначительными, и метод Монтгомери обгоняет простое умножение.
Небольшое ускорение (проценты) можно получить разделением возведения в степень на две операции, как предложил опять же Xaositect на первой странице.
Так что расслабьтесь и пользуйтесь mpz_powm.

[ubik77]

venco в сообщении #808724 писал(а):

Метод Монтгомери применяют именно для умножения по модулю. Без него пришлось бы просто брать модуль (делить). У метода Монтгомери есть большие накладные расходы, поэтому для однократного умножения по модулю он не выгоден. Но если эту операцию надо выполнить много раз с одним и тем же модулем, как это делается при возведении в степень, то потери становятся незначительными, и метод Монтгомери обгоняет простое умножение.

Как это "незначительными"? Множители же каждый раз всё-равно надо приводить. Везде пишут, что он выгоден, если много раз используется один из множителей. В случае возведения остатка в квадрат по модулю этого нет. А в случае умножения по модулю на двойку вообще деление не требуется, достаточно сдвига на один бит и сравнения больше/меньше с модулем (и вычитания если больше). То есть для случая с основанием 2 у Монтгомери нет преимуществ.


Вот ещё статья, вроде бы то что нужно:
http://www.ccrwest.org/gordon/fast.pdf
Надо разбираться.

In Section 3 we show that we can do much better:
Theorem 1. If O(logN/loglogN) powers are precomputed, then we
may compute g^n (0 <= n <= N) using only (1+o(1))logN/loglogN multiplications.
The method works for any group, and in Section 4 we discuss its use in
GF(p^m), where p is a small prime and m is large.

(для вычисления требуется примерно в 8 раз меньше умножений чем разрядность степени в битах)

[B@R5uk]

Даже в методе повторяющихся возведений в квадрат двойка не является чем-то предпочитаемым. Потому что рано или поздно (скорее рано, чем поздно) степень двойки превысит модуль, и при умножении и возведении в квадрат придётся выполнять полноценное умножение, а не просто сдвиг на энное число двоичных разрядов. То есть ускорение за счёт поразрядного сдвига будет работать только до тех пор, пока оперируемые числа меньше чем модуль. Как ни печально, но факт.

[ubik77]

B@R5uk в сообщении #811247 писал(а):

и при умножении и возведении в квадрат придётся выполнять полноценное умножение

Нет, это не так. Только возведение в квадрат. Умножение всегда на двойку.

[B@R5uk]

Ну, вот как-то так (вроде нигде не обсчитался):

$$\begin{align} 2^{458722}\mod458723=\\ =4^{229361}\mod458723=\\ =4^{229360}\cdot4\mod458723=\\ =16^{114680}\cdot4\mod458723=\\ =256^{57340}\cdot4\mod458723=\\ =65536^{28670}\cdot4\mod458723=\\ =402570^{14335}\cdot4\mod458723=\\ =402570^{14334}\cdot234111\mod458723=\\ =356230^{7167}\cdot234111\mod458723=\\ =356230^{7166}\cdot143961\mod458723=\\ =58349^{3583}\cdot143961\mod458723=\\ =58349^{3582}\cdot303536\mod458723=\\ =422418^{1791}\cdot303536\mod458723=\\ =422418^{1790}\cdot28149\mod458723=\\ =141846^{895}\cdot28149\mod458723=\\ =141846^{894}\cdot98062\mod458723=\\ =238213^{447}\cdot98062\mod458723=\\ =238213^{446}\cdot91877\mod458723=\\ =22100^{223}\cdot91877\mod458723=\\ =22100^{222}\cdot173702\mod458723=\\ =328728^{111}\cdot173702\mod458723=\\ =328728^{110}\cdot248185\mod458723=\\ =262151^{55}\cdot248185\mod458723=\\ =262151^{54}\cdot345399\mod458723=\\ =19279^{27}\cdot345399\mod458723=\\ =19279^{26}\cdot124253\mod458723=\\ =114211^{13}\cdot124253\mod458723=\\ =114211^{12}\cdot4655\mod458723=\\ =364016^{6}\cdot4655\mod458723=\\ =5030^{3}\cdot4655\mod458723=\\ =5030^{2}\cdot19777\mod458723=\\ =71135\cdot19777\mod458723=\\ =392177\\ \end{align}$$

18 операций возведения в квадрат из них степень двойки возводится в квадрат 5 раз. 13 операций умножения, из них только одна -- умножение на степень двойки. И мне кажется, что чем больше разрядов в анализируемом простом числе, тем меньшую долю составляют операции над степенями двойки в общем числе операций.

Или я неправильно понял метод последовательного возведения в квадрат?

[ubik77]

B@R5uk в сообщении #811474 писал(а):

18 операций возведения в квадрат из них степень двойки возводится в квадрат 5 раз. 13 операций умножения, из них только одна -- умножение на степень двойки.

Это неправильный алгоритм. Я же дал ссылку:
http://granitnayki.com/?p=212

Число 458722 в двоичном виде 1101111111111100010.
Левый бит отбрасываем, остальные заменяем: для единицы
пишем SX, для нуля S. Получаем строку
SXSSXSXSXSXSXSXSXSXSXSXSXSSSSXS.
Идём слева направо. S - означает возвести в квадрат по модулю 458723,
X - умножить число на 2 по модулю 458723 (то есть сдвинуть влево на 1 бит
и вычесть модуль если стало больше модуля).

Начинаем с двойки и получаем по шагам:

S 4
X 8
S 64
S 4096
X 8192
S 135306
X 270612
S 314824
X 170925
S 205201
X 410402
S 18971
X 37942
S 122590
X 245180
S 335588
X 212453
S 227624
X 455248
S 148827
X 297654
S 143496
X 286992
S 234691
X 10659
S 309700
S 156653
S 316801
S 244600
X 30477
S 392177

18 возведений в квадрат по модулю
13 сдвигов влево на один бит (потом сравнение и если нужно вычитание)

[B@R5uk]

А! Понял. Степень надо расчленять не с конца, а с начала. В библиотеке, что вы используете, есть быстрая функция умножения по модулю?

[ubik77]

B@R5uk в сообщении #811722 писал(а):

А! Понял. Степень надо расчленять не с конца, а с начала. В библиотеке, что вы используете, есть быстрая функция умножения по модулю?

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