Moim problemem jest obliczenie(g^x) mod p szybko w JavaScript, gdzie^ jest potęgowaniem,mod jest operacją modulo. Wszystkie dane wejściowe są nieujemnymi liczbami całkowitymi,x ma około 256 bitów ip jest liczbą pierwszą 2048 bitów ig może mieć do 2048 bitów.

Większość oprogramowania, które znalazłem, może to zrobić w JavaScript, wydaje się korzystać z biblioteki JavaScript BigInt (http://www.leemon.com/crypto/BigInt.html). Wykonanie pojedynczego wykładnika o takiej wielkości w tej bibliotece zajmuje około 9 sekund w mojej wolnej przeglądarce (Firefox 3.0 z SpiderMonkey). Szukam rozwiązania, które jest co najmniej 10 razy szybsze. Oczywisty pomysł wykorzystania kwadratów i mnożenia (potęgowanie przez kwadraty,http://en.wikipedia.org/wiki/Exponentiation_by_squaring) jest zbyt wolny dla liczb 2048-bitowych: wymaga do 4096 mnożeń.

Aktualizacja przeglądarki nie wchodzi w grę. Korzystanie z innego języka programowania nie wchodzi w grę. Wysyłanie numerów do usługi internetowej nie jest opcją.

Czy wdrożono szybszą alternatywę?

Aktualizacja: Wykonując dodatkowe przygotowania (tj. Prekompilując kilkaset uprawnień) zgodnie z zaleceniami artykułuhttp://www.ccrwest.org/gordon/fast.pdf wspomniana poniżej odpowiedź jest możliwa do 2048-bitowego modułowego potęgowania z wykorzystaniem co najwyżej 354 modularnych mnożeń. (Tradycyjna metoda kwadratowa i mnożąca jest znacznie wolniejsza: wykorzystuje maksymalnie 4096 mnożeń modułowych.) W ten sposób przyspiesza się modułowe potęgowanie 6 razy w Firefoksie 3.0 i 4 razy w Google Chrome. Powodem, dla którego nie uzyskujemy pełnego przyspieszenia 4096/354, jest to, że modułowy algorytm wykładniczy BigInt jest już szybszy niż kwadratowy i mnożony, ponieważ wykorzystuje redukcję Montgomery'ego (http://en.wikipedia.org/wiki/Montgomery_reduction).

Aktualizacja: Począwszy od kodu BigInt, wydaje się, że warto robić dwa poziomy zoptymalizowanego ręcznie (i wstawionego) mnożenia Karatsuba (http://en.wikipedia.org/wiki/Karatsuba_algorithm), a dopiero potem powrócić do mnożenia podstawowego 32768 O (n ^ 2) zaimplementowanego w BigInt. Przyspiesza to mnożenie o współczynnik 2,25 dla 2048-bitowych liczb całkowitych. Niestety, operacja modulo nie staje się szybsza.

Aktualizacja: Wykorzystanie zmodyfikowanej redukcji Barretta zdefiniowanej whttp://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf oraz moce mnożenia i prekomputera Karatsuba (zgodnie z definicją whttp://www.ccrwest.org/gordon/fast.pdf), Mogę zmniejszyć czas potrzebny na pojedyncze mnożenie od 73 sekund do 12,3 sekundy w Firefoksie 3.0. Wydaje się, że to najlepsze, co mogę zrobić, ale wciąż jest zbyt wolne.

Aktualizacja: Interpreter ActionScript 2 (AS2) w Flash Playerze nie jest warty użycia, ponieważ wydaje się być wolniejszy niż interpreter JavaScript w Firefoksie 3.0: dla Flash Playera 9 wydaje się być 4,2 razy wolniejszy, a dla Flash Playera 10, wydaje się być 2,35 razy wolniejszy. Czy ktoś zna różnicę prędkości między ActionScript2 a ActionScript3 (AS3) dla chrupiącego numeru?

Aktualizacja: Interpreter ActionScript 3 (AS3) w Flash Playerze 9 nie jest warty użycia, ponieważ ma prawie taką samą szybkość jak JavaScript w Firefoksie 3.0.

Aktualizacja: interpreter ActionScript 3 (AS3) w programie Flash Player 10 może być do 6,5 razy szybszy niż interpreter JavaScript w przeglądarce Firefox 3.0, jeśliint jest używany zamiastNumber, iVector.<int> jest używany zamiastArray. Przynajmniej było 2,41 razy szybsze przy mnożeniu 2048-bitowych liczb całkowitych. Warto więc wykonać modułowe potęgowanie w AS3, wykonując je w Flash Player 10, jeśli jest dostępny. Pamiętaj, że jest to wolniejszy niż V8, interpreter JavaScript w przeglądarce Google Chrome. Widziećhttp://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html dla porównania prędkości różnych implementacji języka programowania i JavaScript.

Aktualizacja: Istnieje bardzo szybkie rozwiązanie Java, które można wywołać z JavaScript przeglądarki, jeśli zainstalowana jest wtyczka Java. Następujące rozwiązanie jest około 310 razy szybsze niż czysta implementacja JavaScript przy użyciu 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>

Czy każdy może przetłumaczyć ten kod na Silverlight (C #)?