Самое быстрое модульное возведение в степень в JavaScript

StackOverflow https://stackoverflow.com/questions/1450608

Вопрос

Моя проблема состоит в том, чтобы вычислить (g^x) mod p быстро в JavaScript, где ^ является возведением в степень, mod является операцией по модулю.Все входные данные представляют собой неотрицательные целые числа, x имеет около 256 бит, и p является простым числом из 2048 бит, и g может содержать до 2048 бит.

Большинство программ, которые я нашел, которые могут делать это на JavaScript, похоже, используют библиотеку JavaScript BigInt (http://www.leemon.com/crypto/BigInt.html).Выполнение одного возведения в степень такого размера с помощью этой библиотеки занимает около 9 секунд в моем медленном браузере (Firefox 3.0 с SpiderMonkey).Я ищу решение, которое будет как минимум в 10 раз быстрее.Очевидная идея использования возведения в квадрат и умножения (возведение в степень путем возведения в квадрат, http://en.wikipedia.org/wiki/Exponentiation_by_squaring) слишком медленный для 2048-битных чисел:для этого требуется до 4096 умножений.

Обновление браузера - это не вариант.Использование другого языка программирования - это не вариант.Отправка номеров в веб-службу невозможна.

Есть ли более быстрая альтернатива?

Обновить:Выполнив некоторые дополнительные приготовления (т. е.предварительное вычисление нескольких сотен степеней), как рекомендовано в статье http://www.ccrwest.org/gordon/fast.pdf упомянутый в приведенном ниже ответе outis, можно выполнить 2048-битное модульное возведение в степень, используя не более 354 модульных умножений.(Традиционный метод возведения в квадрат и умножения работает намного медленнее:он использует максимум 4096 модульных умножений.) Это ускоряет возведение в степень по модулю в 6 раз в Firefox 3.0 и в 4 раза в Google Chrome.Причина, по которой мы не получаем полного ускорения 4096/354, заключается в том, что модульный алгоритм возведения в степень BigInt уже быстрее, чем возведение в квадрат и умножение, потому что он использует редукцию Монтгомери (http://en.wikipedia.org/wiki/Montgomery_reduction).

Обновить:Исходя из кода BigInt, кажется целесообразным выполнить два уровня ручной оптимизации (и встроенного) Умножение Карацубы (http://en.wikipedia.org/wiki/Karatsuba_algorithm), и только затем вернитесь к умножению base-32768 O(n^ 2), реализованному в BigInt.Это ускоряет умножение в 2,25 раза для 2048-битных целых чисел.К сожалению, операция по модулю не становится быстрее.

Обновить:Используя модифицированное сокращение Барретта, определенное в http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf а также умножение Карацубы и предварительные вычислительные мощности (как определено в http://www.ccrwest.org/gordon/fast.pdf), я могу сократить время, необходимое для однократного умножения, с 73 секунд до 12,3 секунды в Firefox 3.0.Кажется, это лучшее, что я могу сделать, но это все еще слишком медленно.

Обновить:Интерпретатор ActionScript 2 (AS2) во Flash Player использовать не стоит, потому что он кажется медленнее, чем интерпретатор JavaScript в Firefox 3.0:для Flash Player 9 это работает в 4,2 раза медленнее, а для Flash Player 10 - в 2,35 раза медленнее.Кто-нибудь знает разницу в скорости между ActionScript2 и ActionScript3 (AS3) для обработки чисел?

Обновить:Интерпретатор ActionScript 3 (AS3) во Flash Player 9 не стоит использовать, потому что он имеет примерно ту же скорость, что и JavaScript в Firefox 3.0.

Обновить:Интерпретатор ActionScript 3 (AS3) в Flash Player 10 может работать в 6,5 раз быстрее, чем интерпретатор JavaScript в Firefox 3.0, если int используется вместо Number, и Vector.<int> используется вместо Array.По крайней мере, это было в 2,41 раза быстрее для 2048-битного умножения больших целых чисел.Так что, возможно, стоило бы выполнить модульное возведение в степень в AS3, выполнив его во Flash Player 10, если таковой имеется.Пожалуйста, обратите внимание, что это все еще медленнее, чем V8, интерпретатор JavaScript Google Chrome.Видишь http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html для сравнения скорости различных реализаций языков программирования и JavaScript.

Обновить:Существует очень быстрое Java-решение, которое может быть вызвано из JavaScript браузера, если установлен Java-плагин.Следующее решение примерно в 310 раз быстрее, чем чистая реализация JavaScript с использованием BigInt.

<body>hi0
<script type="text/javascript">
document.body.innerHTML += '<br>hi1';
if ('object'==typeof java) {
  var x = new java.math.BigInteger("123456789123456789", 10);
  var p = new java.math.BigInteger("234567891234567891", 10);
  var g = new java.math.BigInteger("3", 10);
  var v = x.modPow(x, p);
  document.body.innerHTML += '<br>' + v.toString();
  document.body.innerHTML += '<br>' + v.toString(16);
} else {
  document.body.innerHTML += '<br>java plugin not installed';
}
</script></body>

Кто-нибудь может перевести этот код на Silverlight (C #)?

Это было полезно?

Решение

Будет ли приемлема какая-либо другая клиентская технология, которая может быть вызвана из JS, например Java-апплет или Flash-ролик?БигИнт подход это уже довольно быстро.Вы можете настроить BigInt, или вы можете попробовать другой алгоритм, но вы, вероятно, не получите улучшения на порядок.

Другие советы

Я использую "%" для модульного (mod) и "/" для целочисленного деления.Пусть функция f(p, g, x, r) вычисляет (r*g ^ x)%p при условии, что rf() может быть реализован как:

bigint_t f(p,g,x,r) {
  bigint_t i, z = g, y;
  for (i = 1; i < x; ++i) {
    y = z; z *= g;
    if (z > p) break;
  }
  if (i >= x - 1) return r*z%p; // g^x*r%p = g^x*r
  else return f(p,y,x/i,g^(x%i)*r%p); // reduce to (r*g^(x%i)%p)*(g^i)^(x/i)%p
}

Эта процедура включает в себя немного больше вычислений, но каждое целое число меньше 4096 бит, что обычно намного меньше, чем g ^ x.Я считаю, что это могло бы быть более эффективным, чем прямой расчет.Также обратите внимание, что g ^ (x% i) может быть вычислено более быстрым способом, потому что мы вычислили g ^ (i + 1).

Редактировать:видишь этот пост.Мехрдад дает правильное (и лучшее) решение.

Почему бы не сделать это на стороне сервера в каком-нибудь веб-сервисе, используя более подходящий язык, такой как C?Тогда время будет равняться времени на один переход туда и обратно (менее 9 секунд), плюс время, необходимое серверу для вычисления результата с использованием некоторой библиотеки BigInt в машинном коде.Скорее всего, это будет намного быстрее.

Попробуйте это модульное сокращение Montgomery от http://code.google.com/p/bi2php/ на JavaScript.

Я бы хотел посмотреть исходный код вашей модифицированной библиотеки BigInt - доступна ли она где-нибудь?

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top