如何处理C中的大量数字

问题描述

我正在用C语言编写RSA加密算法。我不打算在任何地方生产它，主要是为了扩大我对加密的理解。

I am writing an RSA encryption algorithm in C. Im not planning to put it in production anywhere, it is mainly just so I can broaden my understanding of encryption.

如何处理RSA产生的大量数字？即使使用相对较小的私钥（例如103）执行解密时，我仍然遇到以下问题：

How do I deal with the massive numbers that RSA generates? Even when performing decryption with a relatively small private key like 103, I still have the issue of dealing with things like this:

存储这种大小的数字的最佳方法是什么？使用标准库有什么办法吗？
。

What is the best way to store a number of that size? Is there any way to do it using standard libraries?.

推荐答案

方法错误。 67 ^ 103 mod 143 不需要先计算 67 ^ 103 。

Wrong approach. 67^103 mod 143 does not need to first calculate 67^103.

循环计算模，一次计算1位指数。

Calculate the modulo in a loop, 1 bit of exponent at a time.

uint32_t powmod(uint32_t base, uint32_t expo, uint32_t mod) {

  // % mod need only for the cases expo==0, mod<=1
  uint32_t y = 1u % mod;

  while (expo) {
    if (expo & 1u) {
      y = ((uint64_t) base * y) % mod;
    }
    expo >>= 1u;
    base = ((uint64_t) base * base) % mod;
  }

  return y;
}

int main(void) {
  printf("%lu",(unsigned long)  powmod(67, 103, 143));
}

输出

89

这篇关于如何处理C中的大量数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！