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

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

11 голосов
/ 20 сентября 2009

Моя задача - быстро вычислить (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 int Firefox 3.0.

Обновление: интерпретатор ActionScript 3 (AS3) в Flash Player 10 может быть в 6,5 раз быстрее, чем интерпретатор JavaScript в Firefox 3.0, если вместо Number используется int, а вместо 1010 * 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 #)?

Ответы [ 5 ]

4 голосов
/ 21 сентября 2009

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

3 голосов
/ 20 сентября 2009

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

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).

РЕДАКТИРОВАТЬ: см. этот пост . Мерада дает правильное (и лучшее) решение.

2 голосов
/ 19 октября 2009

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

2 голосов
/ 20 сентября 2009

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

1 голос
/ 29 декабря 2009

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

...