問題タブ [modular-arithmetic]

これは私が学校を通してやっている課題のためです。秘密鍵の生成に問題があります。私の主な問題は、方程式同士の関係を理解することです。すべてをセットアップするには、次のものが必要です。

ここから n ( phi(n)) の totient が得られ、これは 3120 に等しいので、素数 e を選択できます。ここで、1 < e < 3120

十分に簡単です。

私の課題では、 が認識されていますがd = 2753、この値を任意に生成できるようにする必要があります。

今、ここが私が困っているところです。私は理解するためにウィキペディアを熟読してきましたが、どこかで何かが接続されていません。私たちの私的指数であるの剰余乗法逆数を見つける必要があることはわかっています。e (mod phi(n))d

ウィキペディアを読むと、拡張ユークリッド アルゴリズムを使用するために必要な mmi を見つけるように指示されます。次のようにPythonでアルゴリズムを実装しました：

これは私が迷っているところです。私の理解では、式ax + bx = gcd(a, b) = 1は同じe*x + phi(n)*y = gcd(e, phi(n)) = 1です。を呼び出して、x と yegcd(e, phi(n))を取得します。[-367, 2]

ここから先は正直、どこに行けばいいのかわかりません。この同様の質問を読んだことがありますが、いくつかの置換が行われていることがわかりますが、それらの数が得た答えや最初に使用した値にどのように関連するのかわかりません。誰かがここから何をする必要があるかを実用的に説明できますか? (実用的に言うと、実際のコードがないことを意味します。疑似コードは問題ありませんが、実際のコードを取得した場合、割り当てられた盗作なしでは学ぶことができません。これは大きな問題です)。

いつものように、どんな助けも本当に感謝しています。みんな、ありがとう！

(そして、はい、私はこれらを見てきました: RSA: 拡張ユークリッド アルゴリズムを使用した秘密鍵の計算とRSA暗号化では、p、q、e、および c を指定して d を見つけるにはどうすればよいですか? )

式を満たす最初の n を計算する最速の方法は何ですか?

a^n mod m = 1

ここで、a、n、m は素数または複合 mod です: はモジュラス演算子です

n!modulo p を計算するために次のコードを書きました... n と p が近いと仮定すると...しかし、かなり面白い方法で実行されているため、バグを理解できません..どこかにオーバーフローがあります..制約は1 < P <= 2*10^9

1 <= N <= 2*10^9 ですが、いくつかのケースでは問題なく動作します...エラーの可能性があります。私は使用しました

p素数です....そしてウィルソンの定理(p-1)! mod p = p-1

Cで (2^101100111000)%1000000007 を見つける方法を教えてもらえますか? 数値を 2 進数 (1<=N<=600000) に変換し、1000000007 を法として 2^(N の 2 進数表現) を求める問題があります。

私はこのリンクをウィキペディアの多数のモジュロから研究してきました。ここに疑似コードがあります。

wiki の説明がわかりません。exp%2 が偶数か奇数かを確認する必要があるのはなぜですか。また、なぜ私は3つの操作を行っているのですか?