最快模指数

Question

所面临的挑战是在任何开放源码中编写代码，这些代码可以在linux上使用，这是您选择的执行模块化幂运算的语言。输入将是两个随机选择的2048位正整数，数字x和y和2048位素数z。

def pow_mod(x, y, z):
    n = 1
    while y:
        if y & 1:
            n = n * x % z
        y >>= 1
        x = x * x % z
    return n

代码应该接受一个文件，其中的三个数字分别放在不同的行上，并将结果输出到标准输出。当然，您也不能使用任何库进行模幂运算。

在我的计算机上运行速度最快的代码平均超过100次。

对于那些想要精确计时的人来说，最好的方法可能是计时代码实际出现在您提供的代码中，而您的代码只需重复100次(没有欺骗:)。这避免了启动管理费用方面的任何问题。

Answer 1

C++/asm

在我的笔记本电脑上运行了大约7毫秒。与GMP相距不到2的因子，后者是针对此任务进行的重大优化。

使用蒙哥马利还原快速计算模块缩减。使用python脚本生成x86程序集来执行2048位操作(乘法、添加等)大量的直线代码。

代码大约270行，有点大，粘贴在一个答复框中。下载它这里。