2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 16:50 


15/06/13
31
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 и больше. Но оказалось что это проверить нельзя.

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 17:53 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 18:14 


15/06/13
31
venco в сообщении #808708 писал(а):
Самое медленное в возведении в степень по большому модулю - вычисление остатка от деления. В gmp для ускорения этой операции используют Montgomery reduction, т.к. в случае многократного деления накладные расходы становятся незначительны.

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

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

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

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 18:44 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 19:07 


15/06/13
31
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 раз меньше умножений чем разрядность степени в битах)

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение08.01.2014, 11:44 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение08.01.2014, 16:36 


15/06/13
31
B@R5uk в сообщении #811247 писал(а):
и при умножении и возведении в квадрат придётся выполнять полноценное умножение

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение08.01.2014, 19:41 
Аватара пользователя


26/05/12
816
приходит весна?
Ну, вот как-то так (вроде нигде не обсчитался):
$$\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 операций умножения, из них только одна -- умножение на степень двойки. И мне кажется, что чем больше разрядов в анализируемом простом числе, тем меньшую долю составляют операции над степенями двойки в общем числе операций.

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение08.01.2014, 21:53 


15/06/13
31
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 сдвигов влево на один бит (потом сравнение и если нужно вычитание)

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение09.01.2014, 09:16 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение09.01.2014, 11:03 


15/06/13
31
B@R5uk в сообщении #811722 писал(а):
А! Понял. Степень надо расчленять не с конца, а с начала. В библиотеке, что вы используете, есть быстрая функция умножения по модулю?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3, 4

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group