ユークリッドの互徐法

質問

p と q　は素数とします。
1=gcd(e,(p-1)(q-1))
を満たす最小のe(e>1)はどうやって出せばいいですか。
まだユークリッドの互徐法の使い方に慣れていないので、どうやればいいかわかりません＾＾；
たとえば、p=5 q=7のときどうすればいいでしょう。

回答No.2

stomachman · ベストアンサー

#1のご回答の通りと思いますが、

●gcd(e,b)=1 とはどういう意味かつーと、「eとbを共に割り切るような自然数は1しかない」ということであり、つまり「eとbが互いに素」て意味です。だからご質問の問題は「b=(p-1)(q-1)のとき、eとbが互いに素であるような最小のeは何か？」です。

●ここで、eは素数である。なぜなら、もし「eとbが互いに素であるような最小のe」が合成数であって
e = st (s,t>1)
と分解できるとすると、eより小さいsについて「sとbが互いに素」であるから、eは「eとbが互いに素であるような最小のe」ではなかった事になるからです。

●さて、bを素因数分解したものを以下のように表してみましょう。
n番目の素数をP[n]と書くことにし、
b=(P[1]^k[1])(P[2]^k[2])...(P[N]^k[N])（ただしk[n]≧0）
そうしますと、k[n]=0であるような最小のnを見つければ、P[n]はbの素因数として含まれていない最小の素数である。だから、
gcd(P[n],b)=1
であり、しかもP[n]はgcd(e,b)=1を満たすeの内で最小である。

●という訳で、問題は
「bの素因数として含まれていない最小の素数は何か？」
ということに帰着します。
すなわち、bを素数P[1]=2,P[2]=3,P[3]=5,...で順番に割ってみる、というテストをやって、初めて見つかった割り切れないやつが、eってことです。プログラム風に書くと：

n:=1
loop
　r:=b÷P[n]を計算する。
　if (b÷P[n]が割り切れなかったら) then P[n]が答である。（終わり）
　n:=n+1
end loop

「最悪」の場合は
b=(P[1]^k[1])(P[2]^k[2])...(P[N]^k[N]) , （n=1,2,...,Nについてk[n]＞0）
という場合で、このとき「gcd(e,b)=1となる最小のe」は P[N+1]になります。ご質問の例に挙げられたのは
b=24
で、これはたまたま、この「最悪」の場合に該当します。

●さて、bがP[m]で割り切れたとしましょう。すると、以後、bの代わりに(b/P[m])をテストしても良い。割り切れると分かったら実際に割っておけば、（特にbが何万桁もあるような時には）計算が楽になりそうです。

n:=1
loop
　r:=b÷P[n]を計算する。
　if (b÷P[n]が割り切れなかったら) then
　　P[n]が答である。（終わり）
　else
　　repeat
　　　b:=r;
　　　r:=b÷P[n]を計算する。
　　until b÷P[n]が割り切れない
　　n:=n+1
　end if
end loop

●ところで、ご質問では
b=(p-1)(q-1)
だから、bが合成数であるばかりか、(p-1)も(q-1)も合成数です。ゆえに、「(p-1)の素因数にも(q-1)の素因数にも含まれない最小の素数eは何か」という問題を解けば良い。ということは、(p-1)と(q-1)を素数P[1]=2,P[2]=3,P[3]=5,...で順番に割ってみて、初めて見つかった「どっちも割り切れないやつ」が、eってことです。

x:=p-1
y:=q-1
n:=1
loop
　r:=x÷P[n]を計算する。
　s:=y÷P[n]を計算する。
　if (x÷P[n]が割り切れず、しかもy÷P[n]が割り切れなかったら) then P[n]が答である。（終わり）
　n:=n+1
end loop

もちろんこの場合も、割り切れると分かったら実際に割っておく、という手を組み込むことができます。

x:=p-1
y:=q-1
n:=1
loop
　r:=x÷P[n]を計算する。
　s:=y÷P[n]を計算する。
　if (x÷P[n]が割り切れず、しかもy÷P[n]が割り切れなかったら) then
　　P[n]が答である。（終わり）
　else
　　while (x÷P[n]が割り切れる）
　　　x:=r;
　　　r:=y÷P[n]を計算する。
　　end while
　　while (y÷P[n]が割り切れる）
　　　y:=s;
　　　s:=y÷P[n]を計算する。
　　end while
　end if
　n:=n+1
end loop

●質問のご真意を読みかねるところもある気がするので、「自信なし」です。

お礼

ありがとうございます。簡単に言えば最大公約数をもとめるものだったんですね・・・
暗号化理論という分野の問題だったのですが、授業でやったときは、

gcd(x,y)=sa+tb　（∃s,t)
に分解するようなa,bがある。

という説明をうけたものですから、「互いに素」という概念に気づきませんでした。
あとは大丈夫そうです。
ありがとうございました

回答No.1

noname#24477

元の問題はどんな問題でしょう？
互除法を使えという問題ですか？

最大公約数が１ということなので
ｐ－１とｑ－１を素因数に分解しておいて
そこに含まれない最小の素数を考えればいいと思いますが。

p=5,q=7のとき(p-1)(q-1)＝４＊６＝2^3*3
だからe=5とすればよい。

私が問題を勘違いしているかもしれないので
自信なしにしておきます。

追記　ゴジョホウの漢字に気をつけてください。

お礼

なるほど、ありがとうござます。
字の方は今後気をつけます＾＾；