个人中心
文章发布
退出
作者热门文章
- android - RelativeLayout 背景可绘制重叠内容
- android - 如何链接 cpufeatures lib 以获取 native android 库？
- java - OnItemClickListener 不起作用，但 OnLongItemClickListener 在自定义 ListView 中起作用
- java - Android 文件转字符串
30
4
我的问题是在 JavaScript 中快速计算 (g^x) mod p，其中 ^ 是求幂，mod 是模运算。所有输入都是非负整数，x 大约有 256 位，p 是 2048 位的质数，g 最多可以有 2048 位。
我发现的大多数可以在 JavaScript 中执行此操作的软件似乎都使用 JavaScript BigInt 库 (http://www.leemon.com/crypto/BigInt.html)。在我的慢速浏览器(带有 SpiderMonkey 的 Firefox 3.0)上，用这个库进行一次这样大小的幂运算大约需要 9 秒。我正在寻找至少快 10 倍的解决方案。对于 2048 位数字，使用平方和乘法(通过平方求幂，http://en.wikipedia.org/wiki/Exponentiation_by_squaring)的明显想法太慢:它需要多达 4096 次乘法。
升级浏览器不是一种选择。使用另一种编程语言不是一种选择。将号码发送到 Web 服务不是一种选择。
是否有更快的替代方案实现？
更新:按照下面 outis 的回答中提到的文章 http://www.ccrwest.org/gordon/fast.pdf 的建议，通过做一些额外的准备工作(即预先计算几百次幂)，可以对 2048 位模幂运算最多只使用 354 个模乘。 (传统的平方和乘法方法要慢得多:它使用最多 4096 次模乘。)这样做在 Firefox 3.0 中将模幂运算速度提高了 6 倍，在 Google Chrome 中提高了 4 倍。我们没有获得 4096/354 的完全加速的原因是 BigInt 的模指数算法已经比平方乘法更快，因为它使用蒙哥马利减少 (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 倍。不幸的是，模运算并没有变得更快。
更新:使用 http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf 和 Karatsuba 乘法和预计算幂(定义在 http://www.ccrwest.org/gordon/fast.pdf 中)中定义的修改后的 Barrett 缩减，我可以在 Firefox 3.0 中将单次乘法所需的时间从 73 秒缩短到 12.3 秒。这似乎是我能做的最好的，但它仍然太慢。
更新:Flash Player 中的 ActionScript 2 (AS2) 解释器不值得使用，因为它似乎比 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 差不多。
更新:如果使用 int 代替 Number 并且使用 Vector.<int> 代替 Array ，Flash Player 10 中的 ActionScript 3 (AS3) 解释器可以比 Firefox 3.0 中的 JavaScript 解释器快 6.5 倍。 2048 位大整数乘法至少要快 2.41 倍。因此，可能值得在 AS3 中进行模幂运算，如果可用，在 Flash Player 10 中执行它。请注意，这仍然比 Google Chrome 的 JavaScript 解释器 V8 慢。有关各种编程语言和 JavaScript 实现的速度比较，请参阅 http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.html。
更新:有一个非常快速的 Java 解决方案，如果安装了 Java 插件，可以从浏览器的 JavaScript 调用。以下解决方案比使用 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>
最佳答案
其他一些可从 JS 调用的客户端技术，例如 Java 小程序或 Flash 电影，是否可以接受？ BigInt 的 approach已经相当快了。您可以调整 BigInt，或者您可以尝试 different algorithm ，但你可能不会得到一个数量级的改进。
关于javascript - JavaScript 中最快的模幂运算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1450608/
30
4
0
为什么 (defun boolimplies (a b) (or (not a) b)) if called as(boolimplies 'a 'b) 返回 B? 即使我不使用任何 boolean
这个问题已经有答案了: Are there builtin functions for elementwise boolean operators over boolean lists? (5 个回答
我正在寻求帮助以使以下功能看起来更清晰。我觉得我可以通过使用更少的代码行来实现同样的目标。 标题看起来一定很困惑，所以让我详细说明一下。我创建了一个函数，它接受用户输入(即 72+5)，将字符串拆分为
我正在学习 C++ 并尝试为矩阵编写一个 C++ 类，我在其中将矩阵存储为一维 C 数组。为此，我定义了一个 element成员函数根据矩阵元素在数组中的位置访问矩阵元素。然后我重载了 class
我正在学习 C++ 并尝试为矩阵编写一个 C++ 类，我在其中将矩阵存储为一维 C 数组。为此，我定义了一个 element成员函数根据矩阵元素在数组中的位置访问矩阵元素。然后我重载了 class
伙计们，以下内容不起作用 函数返回 true，变量返回 false，但它不会进入 when 子句。我尝试像这样放大括号 但是当我将变量的值设置为 true 并将上面的代码更改为 它进入w
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题. 已关闭 9 年前。 Improve th
我是原生 C 语言的新手，但我没有看到错误。 我尝试在这种情况下使用 if 操作: #define PAGE_A 0 #define PAGE_B 1 int pageID = 0; if (page
我正在从事一个项目，让用户鼠标滚轮移动并知道它向上或向下滚动。在我的代码中，我可以上下移动。但我想将 Action 保存到一个字符串中。例如，如果用户向上向上向下滚动'mhmh' 显示返回“UUD”但
我有一个 MySQL 表 payment我在其中存储客户的所有付款相关数据。表字段为:fileNo , clientName , billNo , billAmount , status 。我想构建一
我的表架构如下: +------+-------+-------+
我有这个(顺便说一句，我刚刚开始学习): #include #include using namespace std; int main() { string mystr; cout << "We
我正在用 bash 构建一个用于 Linux (SLES 11SP3) 的脚本。我想通过使用以下语法查找它的 pid 来检查某个进程是否存在: pid="$(ps -ef | grep -v grep
我有一个包含两列的表格； CREATE TABLE IF NOT EXISTS `QUESTION_CATEGORY_RELATION` ( `question_id` int(16) NOT N
我对 Python 如何计算 bool 语句感到困惑。 例如 False and 2 or 3 返回 3 这是如何评估的？我认为 Python 首先会查看“False and 2”，甚至不查看“or
这个问题在这里已经有了答案: 12 年前关闭。 这可能是非常基本的......但我似乎不明白: 如何 (2 & 1) = 0 (3 & 1) = 1 (4 & 1) = 0 等等.. 上面的这种模式似
无论如何在Haskell中定义如下函数？ or True True = True or True undefined = True or True False
如您所知，TCL 有一些数学函数，例如 罪 , 因 , 和 假设 在 中调用的expr 带有 的命令() 大括号如下: puts [expr sin(1.57)] 现在如何使用 TCL 添加功能 li
让我们考虑两个数组列表。 ArrayList list1 = new ArrayList(); list1.add(1); list1.add(2); list1.add(3); ArrayList
我想包含和排除使用AND和OR的专业知识，包括与AND和OR操作正常工作。但是，当将排除专家与AND和OR一起使用时，返回与3相同的结果计数。我使用的是1.4版 Elasticsearch 。帮助我解
我是一名优秀的程序员,十分优秀！