Vấn đề của tôi là tính (g^x) mod p nhanh chóng trong JavaScript, trong đó ^ là lũy thừa, mod là phép toán modulo. Tất cả đầu vào là số nguyên không âm, x có khoảng 256 bit và p là số nguyên tố 2048 bit và g có thể có tối đa 2048 bit.Số mũ mô đun nhanh nhất trong JavaScript
Hầu hết phần mềm tôi đã tìm thấy có thể làm điều này trong JavaScript dường như sử dụng thư viện JavaScript BigInt (http://www.leemon.com/crypto/BigInt.html). Làm một lũy thừa đơn có kích thước như vậy với thư viện này mất khoảng 9 giây trên trình duyệt chậm của tôi (Firefox 3.0 với SpiderMonkey). Tôi đang tìm một giải pháp nhanh hơn gấp 10 lần. Ý tưởng rõ ràng về việc sử dụng bình phương và nhân (lũy thừa theo bình phương, http://en.wikipedia.org/wiki/Exponentiation_by_squaring) là quá chậm đối với số 2048 bit: nó cần tới 4096 phép nhân.
Nâng cấp trình duyệt không phải là một tùy chọn. Sử dụng ngôn ngữ lập trình khác không phải là một tùy chọn. Gửi các số tới một dịch vụ web không phải là một tùy chọn.
Có giải pháp thay thế nhanh hơn được triển khai không?
Cập nhật: Bằng cách thực hiện một số chuẩn bị bổ sung (ví dụ như bài báo http://www.ccrwest.org/gordon/fast.pdf được đề cập trong câu trả lời của bên dưới, có thể thực hiện cho phép lũy thừa mô-đun 2048 bit chỉ sử dụng tối đa 354 phép nhân mô-đun . (Phương pháp vuông và nhân truyền thống chậm hơn nhiều: nó sử dụng tối đa 4096 phép nhân mô-đun.) Làm như vậy tăng tốc độ lũy thừa mô đun theo hệ số 6 trong Firefox 3.0 và với hệ số 4 trong Google Chrome. Lý do tại sao chúng tôi không nhận được sự tăng tốc đầy đủ của 4096/354 là thuật toán lũy thừa mô-đun của BigInt đã nhanh hơn so với hình vuông và nhân, bởi vì nó sử dụng giảm Montgomery (http://en.wikipedia.org/wiki/Montgomery_reduction).
Cập nhật: Bắt đầu từ mã của BigInt, có vẻ đáng giá khi thực hiện hai phép nhân Karatsuba được tối ưu hóa bằng tay (http://en.wikipedia.org/wiki/Karatsuba_algorithm), và sau đó quay trở lại phép nhân cơ bản-32768 O (n^2) được thực hiện trong BigInt . Điều này tăng tốc nhân với hệ số là 2,25 cho số nguyên 2048 bit. Thật không may, hoạt động modulo không trở nên nhanh hơn.
Cập nhật: Sử dụng giảm Barrett đã sửa đổi được xác định trong http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf và lũy thừa và lũy thừa Karatsuba (như được định nghĩa trong http://www.ccrwest.org/gordon/fast.pdf), tôi có thể giảm thời gian cần thiết cho một phép nhân đơn từ 73 giây xuống 12,3 giây trong Firefox 3.0. Điều này có vẻ là tốt nhất tôi có thể làm, nhưng nó vẫn còn quá chậm.
Cập nhật: Trình thông dịch ActionScript 2 (AS2) trong Flash Player không đáng sử dụng vì nó có vẻ chậm hơn trình thông dịch JavaScript trong Firefox 3.0: cho Flash Player 9, có vẻ chậm hơn 4,2 lần, và cho Flash Player 10, nó có vẻ chậm hơn 2,35 lần. Có ai biết sự khác biệt tốc độ giữa ActionScript2 và ActionScript3 (AS3) cho số chrunching?
Cập nhật: Trình thông dịch ActionScript 3 (AS3) trong Flash Player 9 không đáng sử dụng vì nó có tốc độ tương tự như JavaScript int Firefox 3.0.
Cập nhật: Các ActionScript 3 (AS3) thông dịch viên trong Flash Player 10 có thể nhanh hơn so với phiên dịch JavaScript lên đến 6,5 lần trong Firefox 3.0 nếu int được sử dụng thay vì Number, và Vector.<int> được sử dụng thay vì Array. Ít nhất là 2,41 lần nhanh hơn cho phép nhân số nguyên lớn 2048 bit. Vì vậy, có thể có giá trị khi thực hiện mô đun lũy thừa trong AS3, thực hiện nó trong Flash Player 10 nếu có. Xin lưu ý rằng điều này vẫn chậm hơn V8, trình thông dịch JavaScript của Google Chrome.Xem http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html để so sánh tốc độ của các ngôn ngữ lập trình và triển khai JavaScript khác nhau.
Cập nhật: Có một giải pháp Java rất nhanh, có thể được gọi từ JavaScript của trình duyệt nếu plugin Java được cài đặt. Giải pháp sau đây nhanh hơn khoảng 310 lần so với triển khai JavaScript thuần túy khi sử dụng 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>
Mọi người có thể dịch mã này sang Silverlight (C#) không?
Tôi phải xác nhận rằng BigInt được tối ưu hóa khá tốt. Tôi đã cố gắng để thực hiện phép nhân bằng cách sử dụng thuật toán Karatsuba, nhưng nó trở thành 4 lần chậm như nhân đơn O (n^2) đơn giản của BigInt. – pts
Cảm ơn bạn đã đề cập đến bài báo, có vẻ đầy hứa hẹn. – pts
Sử dụng BigInt.js với các kỹ thuật trong bài viết bạn đã liên kết tôi có thể tăng tốc độ nhân mô đun của các số nguyên 2048 bit theo hệ số 6 trên Firefox 3.0 và hệ số 4 trên Google Chrome. Thật không may, điều này vẫn còn quá chậm đối với tôi, vì vậy tôi phải tìm một giao thức mã hóa khác, mà cần tính toán ít hơn. – pts