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

Моя проблема состоит в том, чтобы вычислить(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, еслиint используется вместоNumber, а такжеVector. используется вместо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-решение, которое можно вызвать из браузера.s JavaScript, если установлен плагин Java. Следующее решение примерно в 310 раз быстрее, чем реализация чистого JavaScript с использованием BigInt.

hi0

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';
}

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

Ответы на вопрос(5)

Ваш ответ на вопрос