2

我在 Mathematica 中实现了一个算法，它使用 PowerMod 来找到模逆。我现在需要在 C 中实现这个算法，我决定使用 gmp 及其函数mpz_powm，这显然是做同样的事情。问题是，我没有得到相同的值。例如，在 Mathematica 上运行时，它会给出：

PowerMod[30030, -1, 43] = 35

而mpz_pwm给出 16。并且：

PowerMod[30030, -1, 71] = 8

而mpz_pwm给出 46。（我希望这些是足够的例子。）我还尝试了各种我设法在网上找到的模块化逆算法，它们也给出了不同的值。不过，我怀疑 Mathematica 是对的。有谁知道这里发生了什么？

4

2 回答 2

2

在这个链接上有一些似乎相关的东西。

简而言之，mpz_pwm 似乎将 -1 解释为无符号短 2^16-1。此链接的线程中的一个响应来自 GMP 开发人员，大意是这是文档中的错误。

至于 2^16-1，我是通过一些实验得到的。

PowerMod[30030,2^16-1,43]                                               

(* Out[5]= 16 *)

到目前为止，一切都很好。当第三个参数是 71 时它就崩溃了。但PowerMod[30030, -1, 71]实际上不是 8。当第三个参数是 79 时成立。而且我们仍然不PowerMod[30030, 2^16-1,79]等于 46：当第三个参数是 73 时成立。所以我猜这些是您实际powerMod分别提供给和 mpz_pwm 的参数。

如果 GMP 没有直接做你需要的功能，你可以从扩展的 GCD 中得到模逆。我将展示在 Mathematica 中使用的代码，但我确信它可以适应手头的目的。

myModularInverse[n_,p_] := With[{inv=ExtendedGCD[n,p][[2,1]]},
  If[inv>0, inv, inv+p]]

快速示例：

myModularInverse[30030, 43]                                            

(* Out[28]= 35 *)

myModularInverse[30030, 79]                                            

(* Out[29]= 8 *)

编辑：更多挖掘表明 GMP 有一个函数 mpz_invert 似乎可以做这里想要的。请参阅 GMP数论函数。还有一个 gmp_invert 函数，我猜它在 gmp 层次结构中处于更高级别。

于 2014-08-13T15:04:59.663 回答
1

本机 GMPmpz_powm不直接处理负指数。您需要使用 计算倒数mpz_invert。

我在 gmpy2（GMP 的 Python 包装器）中实现了您想要的行为。我的代码在：

https://code.google.com/p/gmpy/source/browse/trunk/src/gmpy2_pow.c

注意代码：mpz_inoc 和 mpz_cloc 是 mpz_init 和 mpz_clear 的替代品，它们在后台缓存对象。

于 2014-08-13T16:21:19.013 回答