問題タブ [modular-arithmetic]

あるオンライン フォーラムで、次のインタビューの質問を見ました。これに対する良い解決策は何ですか？

5^1234566789893943 の最後の 1000 桁を取得します

この質問は、私がほとんどこの質問の下に書いたコメントに由来します。ここで、ザックは大きな数を法とする大きな数の階乗を計算しています (この質問のために素数であると仮定します)。ザックは階乗の従来の計算を使用しており、乗算ごとに剰余を取ります。

検討すべき代替手段はモンゴメリー乗算であるとほとんどコメントしましたが、それについてもっと考えてみると、この手法が同じ被乗数による複数の乗算を高速化するために使用されているのを見ただけです (特に、ⁿ mod p の計算を高速化するため)。

私の質問は、モンゴメリー乗算を使用して n の計算を高速化できるかどうかです! 大きな n と p の mod p?

質問があります。サーバーとクライアント間の暗号化プロトコルを Diffie-Hellman 問題に基づいて実装しようとしています。

問題は、私がそれをしようとしたとき、私に((t^RsRc) mod p)^(1/Rc mod q) 与えていないことです(t^Rs) mod p。

私はそれをやっていても私に ((t^Rc) mod p)^(1/Rc mod q) t.modPow(Rc, p)).modPow(Rc.modInverse(q), p)与えていないことを確認しましたt。

これは、乗法モジュロ逆数 (モジュロ 10^9+7) を計算するために私が書いた Java プログラムです。ただし、10 より大きい数値の出力として負の数値が返されます。何が問題なのかわかりません。

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

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

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

最近私は拡張されたユークリッドのアルゴリズムを読みました。これは、そのようなNに関する数値の剰余逆数を見つけるために使用されます。MODgcd(N,MOD)=1

しかし、次の場合にモジュラー逆数を見つける方法については疑問がありgcd(N,MOD)!=1ます。

ベクトル n 値があり、リング トポロジがあると見なされる場合は、3 つの隣接する値のグループ n グループに分割したいと考えています。

私がやろうとしていることはこれです:

したがって、n = 10 で i = 1 の場合、グループは [vector(10); ベクトル (1); ベクトル(2)]

ほとんどのプログラミング言語では、mod 演算子を使用するだけでかなり簡単ですが、matlab を使用してこれを行う方法を理解するのに苦労しています。これは、ベクトルの初期インデックスとして 0 を使用しないため、i = 1 の場合、mod (i-1) = 0 これは不正なインデックス値です。また、i = n は mod(n, n) = 0 として問題になります。

私はかなりハックっぽい解決策を考え出しました:

しかし、それはかなりエレガントではなく、それを行うためのより良い方法があるべきだと感じています..

ベクトルインデックスに対してモジュラー演算を実行できる演算子はありますか?