gmp - Mathematica PowerMod inverse と C の mpz_powm

Question

PowerMod を使用して剰余逆数を見つけるアルゴリズムを Mathematica に実装しました。このアルゴリズムを C で実装する必要があり、gmp とその関数mpz_powmを使用することにしました。明らかに同じことを行います。問題は、同じ値が得られないことです。たとえば、Mathematica で実行すると、次のようになります。

PowerMod[30030, -1, 43] = 35

一方、mpz_pwmは 16を返します。

PowerMod[30030, -1, 71] = 8

一方、mpz_pwmは 46 を返します (これらが十分な例であることを願っています)。オンラインで見つけることができたさまざまなモジュラー逆アルゴリズムも試しましたが、それらも異なる値を示します。しかし、Mathematica は正しいと思います。ここで何が起こっているか知っている人はいますか？

Answer 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 の代替品です。