numbers - Octave - 如何处理大数

Question

我正在研究 Octave 的 RSA 算法，但它没有以正确的方式工作。当我尝试使用“^”功能时出现问题。检查下面的示例:

>> mod((80^65), 133)

终端给我:

ans = 0

我无法修复这个问题，这很有趣，因为即使我的系统计算器也返回正确的数字(54)

Answer 1

要以正确的方式计算此值，您可以使用快速幂模算法。在 C++ 中，检查下面的函数 where ->a^b mod m:

int power_modulo_fast(int a, int b, int m)
{
int i;
int result = 1;
int x = a % m;

for (i=1; i<=b; i<<=1)
{
  x %= m;

    if ((b&i) != 0)
      {
    result *= x;
    result %= m;
      }

   x *= x;
}

  return result;
}