2014 dxdy logo

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

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




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


15/06/13
31
$ a^{n-1}\ mod\ n $

Возможно ли ощутимо ускорить эту операцию, если a=2 ?
Я пробовал на библиотеке GMP, особой разницы в скорости
например с a=3 и a=5 не заметил.

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


05/09/12
2587
Два в любой степени в двоичной системе счисления выглядит очень кругло.

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


04/05/09
4582
Можно ускорить умножение непосредственно на двойку - модуль потом легче брать. Соответственно можно выбрать вариант быстрого возведения в степень, которое часто умножает именно на два, и сэкономить на специальном определении модуля.
Это может быть и не сделано в gmp.
А n какого порядка?

-- Сб июн 15, 2013 21:29:15 --

В gmp, похоже, алгоритм оперирует сразу несколькими битами степени, поэтому то, что показатель именно 2, уже неважно.

 Профиль  
                  
 
 Posted automatically
Сообщение16.06.2013, 07:57 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Программирование»
Перенёс в соответствующий раздел

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


15/06/13
31
venco в сообщении #737161 писал(а):
Можно ускорить умножение непосредственно на двойку - модуль потом легче брать. Соответственно можно выбрать вариант быстрого возведения в степень, которое часто умножает именно на два, и сэкономить на специальном определении модуля.
Это может быть и не сделано в gmp.
А n какого порядка?

-- Сб июн 15, 2013 21:29:15 --

В gmp, похоже, алгоритм оперирует сразу несколькими битами степени, поэтому то, что показатель именно 2, уже неважно.

n очень большое по размеру, может быть 500..1000 двоичных разрядов. Эта операция (возведение в степень по модулю) не делается в два приёма (сначала степень, а потом модуль), для больших чисел она считается по специальным алгоритмам, один такой вроде называется "метод квадратов". GMP считает от 1 до 3 секунд. Вот мне интересно, можно ли это ускорить, возможно есть ещё алгоритмы, которые за счёт того, что основание 2, работают быстрее.

P.S. Собственно это тeст Фepма - проверка большого числа на простоту. Если результат равен 1, то с большой вероятностью n простое.

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


06/10/08
6422
При таком размере модуля и степени скорее всего используется представление Монтгомери, а там двойка не лучше остальных чисел.

Каких-то специальных способов для $2^k\operatorname{mod} n$ я не знаю. Можно сначала вычислить $2^{\lceil\log_2 n\rceil} \operatorname{mod} n = 2^{\lceil\log_2 n\rceil} - n$, это будет быстро, а потом возвести его в соответствущую степень $\frac{k}{\lceil\log_2 n\rceil}$ и домножить все на доп. множитель $2^{k\operatorname{mod} \lceil\log_2 n\rceil}$. Возможно, получится быстрее.

Если хочется ускорить, попробуйте использовать mpn_ интерфейс вместо mpz_.

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


15/06/13
31
mpn_powm там есть, но она даже не вынесена в интерфейс. Эти функции (mpn) в основном экономят на обработке аргументов, так что если алгоритм тот же, то вряд ли она работает быстрее чем стандартная mpz_powm. Но попробую.

По вашим советам придётся обрабатывать нецелые числа (например в log2), сомневаюсь что получится приемлемый результат.

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


31/10/08
1244
ubik77
$ (3*3*3*3) \mod n=(((3 \mod n)*3 \mod n)*3 \mod n)*3 \mod n $
И не какие GMP не нужны.
И работать будет в 1000 раз быстрее.

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


15/06/13
31
Pavia в сообщении #737315 писал(а):
ubik77
$ (3*3*3*3) \mod n=(((3 \mod n)*3 \mod n)*3 \mod n)*3 \mod n $
И не какие GMP не нужны.
И работать будет в 1000 раз быстрее.

Это у вас 3 в четвертой степени что-ли? Степень это огромное число, чтобы столько раз повторить это действие - не хватит времени существования вселенной.

P.S. Сейчас посмотрел - самый быстрый действительно метод Монтгомери, но там основание 2 никаких особых выгод не даёт.

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


06/10/08
6422
ubik77 в сообщении #737309 писал(а):
По вашим советам придётся обрабатывать нецелые числа (например в log2), сомневаюсь что получится приемлемый результат.
$\log_2$ - это длина числа в битах (почти)

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


11/03/08
9496
Москва
Pavia


Эээ... Когда ставится такая задача, подразумевается, что показатель степени выражается числом длиной в сотню бит или около того (он может быть, например, ключом шифра).

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


11/01/06
5660
ubik77 в сообщении #737113 писал(а):
$ a^{n-1}\ mod\ n $

Возможно ли ощутимо ускорить эту операцию, если a=2 ?
Я пробовал на библиотеке GMP, особой разницы в скорости
например с a=3 и a=5 не заметил.


Вопрос звучит странно, так как в GMP данная операция осуществляется одной командой - см.
http://gmplib.org/manual/Integer-Expone ... nentiation

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


15/06/13
31
maxal писал(а):
Вопрос звучит странно, так как в GMP данная операция осуществляется одной командой - см.
http://gmplib.org/manual/Integer-Expone ... nentiation

Я это знаю. Меня не устраивает быстродействие этой операции в gmp
для очень больших n, и поэтому ищу способы ускорить для случая a=2.

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


24/05/09

2054
Код:
//возведение в большую степень и деление по модулю
__int64 modpow(__int64 x, __int64 e, __int64 n)
{
__int64 r = 1;

while(e > 0)
  {
  if((e % 2 ) == 1) {r = (r * x) % n;}
  e = e / 2;
  x = (x * x) % n;
  }

return r;
}


Если не ошибаюсь, это функция быстрого вычисления $ (x^e)\mod\ n$

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


15/06/13
31
Alexu007 в сообщении #808119 писал(а):
Код:
//возведение в большую степень и деление по модулю
__int64 modpow(__int64 x, __int64 e, __int64 n)
{
__int64 r = 1;

while(e > 0)
  {
  if((e % 2 ) == 1) {r = (r * x) % n;}
  e = e / 2;
  x = (x * x) % n;
  }

return r;
}


Если не ошибаюсь, это функция быстрого вычисления $ (x^e)\mod\ n$

Это очень похоже на "метод квадратов", но почему-то вычисляется в обратном порядке - с младших битов e к старшим. Вроде бы так не должно работать, но я проверю.
Я тоже думаю в сторону оптимизированного метода квадратов.
Операцию умножение по модулю (x * x) % n можно оптимизировать по специальному алгоритму, должна выполняться в два раза быстрее, а
r = (r * x) % n для x=2 всего лишь сдвиг влево и сравнение с n - больше или меньше.

Но я думаю, что в GMP возведение в степень по модулю тоже делается методом квадратов. Надо посмотреть исходники, возможно там улучшать уже некуда.

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

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



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

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


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

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