RSA暗号で「互いに素」というのは

質問

タイトルどおりです。どうも意味がわかりません。「Ｌと互いに素」とは、Ｌと何を互いっていうのでしょう。
例を使って解説してくれると助かります。
しかも、「Lと互いに素な自然数で最小のもの」を求めないといけないのですが・・・。

回答No.4

neKo_deux · ベストアンサー

> 例えばp=3,q=11でLCM(p-1,q-1)をＬとする場合

LCMは最大公約数の事だったと思いますから、
2(=3-1)と10(=11-1)の最大公約数でL=2となり、

> Ｌと互いに素な自然数で最小のものは３

でＯＫだと思います。

お礼

どうもありがとうございます。

回答No.3

nontitti

★互いに素の定義からＬの正体をを知る
　定義「２つの自然数の、”最大公約数が１”であるときに、二つの自然数の関係を互いに素という」
　この定義から、”Ｌと互いに素”におけるＬは自然数ということになります。
★ＲＳＡ記号とは？
雑駁に言うと
１）二つの大きな素数を求める。これをa,bとする。
２）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.2

oja

互いに素とは最大公約数が1しか無い（公約数が無い)こと言います。

参考URL：

http://www.cybersyndrome.net/rsa/

回答No.1

neKo_deux

「互いに素」は公約数がないという事です。

例えば、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)をＬとする場合
Ｌと互いに素な自然数で最小のものは３ということでいいのですか？