有谁知道对位取模的更好方法吗？

Question

我有 2 个大数，一个大约 4096 位，另一个 2048 位，存储在一个结构中：

 typedef uint32_t word;
 typedef struct BigNumber {
     word words[128];
 } BigNumber;

我必须对这些取模，我能想到的唯一方法是多次减去，但这需要一些时间。

有人知道更好的方法吗？

Answer 1

计算m%n:

modulus(m, n) {
  if (m < n) return m
  elif (m < (n<<1)) return m - n
  else return modulus((modulus(m>>1, n)<<1 + m&1), n)
}

Answer 2

你可以用 a 除以 b 得到整数 x。现在从 a 中减去 x 得到模数。使用任意除数，您将无法绕过除法。对于大除数，这可能比多次减法更快，但除法仍然很昂贵。

对于如此大的数字，您可能还必须手动实施除法算法。那里有一个，它同时产生 qoutient 和余数（模数），但我现在记不起它的名字了。

Answer 3

代码基于 @caf 我的更正。让 OP 编写 4 个辅助函数。

void BigNumber_Shift_Right(BigNumber *x);
void BigNumber_Shift_Left(BigNumber *x);
int BigNumber_Compare(const BigNumber *a, const BigNumber *b);
void BigNumber_SubtractEqual(BigNumber *a, const BigNumber *b);

void BigNumber_ModHalfSizeEqual(BigNumber *A, const BigNumber *B) {
  BigNumber X = *B;
  BigNumber AHalf = *A;
  BigNumber_Shift_Right(&AHalf);

  while (BigNumber_Compare(&X, &AHalf) <= 0) {
    BigNumber_Shift_Left(&X);
  }

  while (BigNumber_Compare(A, B) >= 0) {
    if (BigNumber_Compare(A, &X) >= 0) {
      BigNumber_SubtractEqual(A, &X); 
    }
    BigNumber_Shift_Right(&X);
  }

  // mod is in A
}

有谁知道对位取模的更好方法吗？

Does anyone know a better way for modulo on bits?

c

math

biginteger

modulo