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).이 라이브러리를 사용하여 이러한 크기의 단일 지수화를 수행하는 데는 느린 브라우저(Firefox 3.0 with SpiderMonkey)에서 약 9초가 걸립니다.저는 적어도 10배 더 빠른 솔루션을 찾고 있습니다.제곱과 곱셈(제곱에 의한 지수화, http://en.wikipedia.org/wiki/Exponementiation_by_squaring)은 2048비트 숫자에 비해 너무 느립니다.최대 4096번의 곱셈이 필요합니다.

브라우저 업그레이드는 선택 사항이 아닙니다.다른 프로그래밍 언어를 사용하는 것은 선택 사항이 아닙니다.웹 서비스에 번호를 보내는 것은 옵션이 아닙니다.

더 빠른 대안이 구현되어 있습니까?

업데이트:몇 가지 추가 준비를 수행합니다(예:기사에서 권장하는 대로 수백 개의 거듭제곱을 미리 계산합니다. http://www.ccrwest.org/gordon/fast.pdf 아래 outis의 답변에서 언급했듯이 최대 354개의 모듈러 곱셈만 사용하여 2048비트 모듈러 지수화를 수행할 수 있습니다.(기존의 제곱 및 곱셈 방법은 훨씬 느립니다.최대 4096개의 모듈식 곱셈을 사용합니다.) 이렇게 하면 모듈식 지수 계산 속도가 Firefox 3.0에서는 6배, Google Chrome에서는 4배 빨라집니다.4096/354의 최대 속도 향상을 얻지 못하는 이유는 BigInt의 모듈러 지수 알고리즘이 Montgomery 감소를 사용하기 때문에 이미 제곱 및 곱셈보다 빠르기 때문입니다(http://en.wikipedia.org/wiki/Montgomery_reduction).

업데이트:BigInt의 코드에서 시작하여 두 가지 수준의 직접 최적화된(및 인라인된) Karatsuba 곱셈을 수행하는 것이 가치 있는 것 같습니다(http://en.wikipedia.org/wiki/Karatsuba_algorithm), 그런 다음 BigInt에 구현된 base-32768 O(n^2) 곱셈으로 되돌아갑니다.이렇게 하면 2048비트 정수의 경우 곱셈 속도가 2.25배 빨라집니다.불행하게도 모듈로 연산은 더 빨라지지 않습니다.

업데이트:다음에 정의된 수정된 Barrett 감소를 사용하여 http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf Karatsuba 곱셈 및 사전 계산 능력(에 정의됨) http://www.ccrwest.org/gordon/fast.pdf), Firefox 3.0에서는 단일 곱셈에 필요한 시간을 73초에서 12.3초로 줄일 수 있습니다.이것이 제가 할 수 있는 최선인 것 같지만 여전히 너무 느립니다.

업데이트:Flash Player의 AS2(ActionScript 2) 인터프리터는 Firefox 3.0의 JavaScript 인터프리터보다 느린 것으로 보이기 때문에 사용할 가치가 없습니다.Flash Player 9의 경우 4.2배, Flash Player 10의 경우 2.35배 느린 것으로 보입니다.숫자 처리 시 ActionScript2와 ActionScript3(AS3)의 속도 차이를 아는 사람이 있습니까?

업데이트:Flash Player 9의 ActionScript 3(AS3) 인터프리터는 JavaScript int Firefox 3.0과 속도가 거의 동일하므로 사용할 가치가 없습니다.

업데이트:Flash Player 10의 ActionScript 3(AS3) 인터프리터는 다음과 같은 경우 Firefox 3.0의 JavaScript 인터프리터보다 최대 6.5배 더 빠를 수 있습니다. int 대신에 사용됩니다 Number, 그리고 Vector.<int> 대신에 사용됩니다 Array.2048비트 큰 정수 곱셈에서는 적어도 2.41배 더 빨랐습니다.따라서 AS3에서 모듈식 지수화를 수행하고 가능한 경우 Flash Player 10에서 실행하는 것이 좋습니다.이는 Google Chrome의 JavaScript 인터프리터인 V8보다 여전히 느립니다.보다 http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html 다양한 프로그래밍 언어와 JavaScript 구현의 속도를 비교합니다.

업데이트:Java 플러그인이 설치된 경우 브라우저의 JavaScript에서 호출할 수 있는 매우 빠른 Java 솔루션이 있습니다.다음 솔루션은 BigInt를 사용한 순수 JavaScript 구현보다 약 310배 빠릅니다.

<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#)로 번역할 수 있습니까?

도움이 되었습니까?

해결책

Java 애플릿이나 Flash 동영상과 같이 JS에서 호출할 수 있는 다른 클라이언트 측 기술이 허용됩니까?BigInt의 접근하다 이미 상당히 빠릅니다.BigInt를 조정하거나 다음을 시도해 볼 수 있습니다. 다른 알고리즘, 그러나 아마도 상당한 수준의 개선을 얻지 못할 것입니다.

다른 팁

모듈러(mod)에는 "%"를 사용하고 정수 나누기에는 "/"를 사용합니다.함수 f(p,g,x,r)가 r<p 및 g<p 조건에서 (r*g^x)%p를 계산하도록 합니다.f()는 다음과 같이 구현될 수 있습니다.

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
}

이 루틴에는 약간 더 많은 계산이 포함되지만 각 정수는 일반적으로 g^x보다 훨씬 작은 4096비트 미만입니다.직접 계산하는 것보다 이것이 더 효율적일 수 있다고 생각합니다.또한 g^(x%i)는 g^(i+1)을 계산했기 때문에 더 빠른 방식으로 계산할 수 있습니다.

편집하다:보다 이 게시물.Mehrdad는 올바른 (그리고 더 나은) 솔루션을 제공합니다.

C와 같은 더 적절한 언어를 사용하여 일종의 웹 서비스에서 서버 측을 수행하는 것은 어떻습니까?그러면 시간은 한 번의 왕복 시간(9초 미만)에 서버가 네이티브 코드의 일부 BigInt 라이브러리를 사용하여 결과를 계산하는 시간이 됩니다.이것은 훨씬 더 빠를 가능성이 높습니다.

Montgomery 모듈식 축소를 사용해 보세요. http://code.google.com/p/bi2php/ 자바스크립트에서.

수정된 BigInt 라이브러리의 소스 코드를 보고 싶습니다. 어디에서나 사용할 수 있나요?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top