No.3
- 回答日時:
★互いに素の定義からLの正体をを知る
定義「2つの自然数の、”最大公約数が1”であるときに、二つの自然数の関係を互いに素という」
この定義から、”Lと互いに素”におけるLは自然数ということになります。
★RSA記号とは?
雑駁に言うと
1)二つの大きな素数を求める。これをa,bとする。
2)a*b=c (cを合成数)
3) (a-1)(b-1)と互いに素となる自然数dを求める
4)d*e≡1 mod(a-1)(b-1)なる自然数fを求める
公開鍵として、c,dを、秘密鍵としてeを保存する。
この鍵の有効性の証明とかは、お任せするとして、3)の過程で、互いに素なる数を求めるわけですが、互いに素なる数を求める具体的な方法は、ユークリッド互除法が有効です。これは、検索すれば、すぐわかるでしょう。
他、4)の過程で≡、modなどというものが出ますがこれは合同式というものです。互いに素な数を求めるよりも、合同式の理解の方が難しい気がします。
No.1
- 回答日時:
「互いに素」は公約数がないという事です。
例えば、10と互いに素な数を探してみると、
2…2の約数2と、10=2×5の約数2が存在。
3…公約数は無い。
4…4=2×2の約数が存在。
5…5が公約数。
6…2が公約数。
7…公約数は無い。
8…2が公約数。
9…公約数は無い。
で、10と互いに素な数は3,7,9,11,…となります。
最小なものを探す場合は、素数を小さいほうからチェックしていくようなアルゴリズムがシンプルなものになると思います。
この回答への補足
回答ありがとうございます。
例えばp=3,q=11でLCM(p-1,q-1)をLとする場合
Lと互いに素な自然数で最小のものは3ということでいいのですか?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 大学受験 至急! 数学 整数 なぜ3以上にならないのですか? 3 2023/01/29 12:47
- その他(形式科学) RSA暗号について 1 2022/06/01 00:16
- 数学 最小公倍数と最大公約数の求め方で画像のような計算法があったのですが、理解できません。 なぜ2つ数24 4 2022/04/10 13:37
- 数学 「互いに素であるA、B」と 「一以外に正の公約数をもたない自然数A、B」 の違いはなんですか? 4 2022/08/02 18:32
- 数学 正の約数の個数が20個である最小の自然数を求めよ」 という問題で、(□+1)×(△+1)=20となる 4 2022/07/26 11:58
- 数学 ユークリッドの互除法、合同式の問題について 1 2022/05/08 11:49
- 哲学 ソシュール≒丸山圭三郎の《言語記号の恣意性》説はウソである 6 2022/12/01 06:19
- 高校 レピュニット数の性質についてです。 レピュニット数とは、各桁が1のみの数で、以下1がk桁の数をRkと 3 2023/07/21 19:58
- 介護 在宅酸素療法患者による身障者介護と勤務 1 2023/06/03 11:58
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
べき乗
-
皆さん定義を教えてください 「...
-
強者男性、弱者男性の定義って...
-
「logx^2=2logx」が間違って...
-
最大元と極大元の定義の違いが...
-
ACCESS VBAでインポート定義の場所
-
無限から無限を引いたら何にな...
-
1未満と1以下の違い
-
日本語 ことば ひとまわり ふた...
-
EXCELで定義した名前をVBAで参...
-
Excelファイルの「数式」タブ→...
-
指数関数論
-
全順序集合と半順序集合
-
数学における「定義できない」...
-
交換法則が成り立って、結合法...
-
eの0乗は1ってどういう原理です...
-
フーリエ級数展開の初項はなぜa...
-
0に限りなく近い数は存在するの?
-
ε-δ論法のモヤっと感
-
ゼロと無限大を逆元とする群の...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
皆さん定義を教えてください 「...
-
べき乗
-
1未満と1以下の違い
-
無限から無限を引いたら何にな...
-
理論物理学でよく用いられる地...
-
(-1) ^2πってなんで1じゃないん...
-
ACCESS VBAでインポート定義の場所
-
変数の宣言の名称を教えてくだ...
-
「互いに素」の定義…「1と2は互...
-
日本語 ことば ひとまわり ふた...
-
ACCESS IIF関数 複数条件の設...
-
質問の定義が分からないので確...
-
なぜ、直角三角形ではないのにs...
-
min関数 一橋大学過去問
-
質問の定義が分からないので確...
-
ヘシアンが0の場合どうやって極...
-
excel vba 名前付きセルが存在...
-
数字の1とは何なのか?
-
マイナス7は素数ですか?
-
「logx^2=2logx」が間違って...
おすすめ情報