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

[ubik77]

$ a^{n-1}\ mod\ n $

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

[_Ivana]

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

[venco]

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

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

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

[Deggial]

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

[ubik77]

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

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

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

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

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

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

[Xaositect]

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

Каких-то специальных способов для $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_.

[ubik77]

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

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

[Pavia]

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

[ubik77]

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 никаких особых выгод не даёт.

[Xaositect]

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

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

$\log_2$ - это длина числа в битах (почти)

[Евгений Машеров]

Pavia


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

[maxal]

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

$ a^{n-1}\ mod\ n $

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

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

[ubik77]

maxal писал(а):

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

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

[Alexu007]

//возведение в большую степень и деление по модулю
__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$

[ubik77]

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 возведение в степень по модулю тоже делается методом квадратов. Надо посмотреть исходники, возможно там улучшать уже некуда.