No.2ベストアンサー
- 回答日時:
#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
●質問のご真意を読みかねるところもある気がするので、「自信なし」です。
この回答へのお礼
お礼日時:2004/02/01 08:39
ありがとうございます。簡単に言えば最大公約数をもとめるものだったんですね・・・
暗号化理論という分野の問題だったのですが、授業でやったときは、
gcd(x,y)=sa+tb (∃s,t)
に分解するようなa,bがある。
という説明をうけたものですから、「互いに素」という概念に気づきませんでした。
あとは大丈夫そうです。
ありがとうございました
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
全員と同じグループを経験でき...
-
以下の問題の解答・解説を教え...
-
数学Aの確率
-
【放物線の問題】
-
x.>0ときγ(x)が最小値となるxの...
-
2進数のバイアス表現について
-
数学の対戦問題で最少の勝ち数...
-
最大元と最小元をもつことの証...
-
EXCEL ドラッグしたセル...
-
2次関数の問題の場合分けで理解...
-
高一の数学です。以下の2問の回...
-
対数関数の問題です
-
2つの放物線間の最短距離
-
0は公約数?
-
2次関数の最小値、最大値を求...
-
至急!!二次関数について aは...
-
3次元での点群に対する最小二...
-
3で割ると2余り、7で割ると4余...
-
Gnuplot 最小二乗フィッティン...
-
35%と65%に分けるには最低何人...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
全員と同じグループを経験でき...
-
3次元での点群に対する最小二...
-
問題文は解答欄に載せます。 四...
-
2次関数の応用
-
三角関数の問題なのですが257の...
-
中学受験用の小5算数の問題です
-
高校数学1の問題集に、2次関数...
-
3で割ると2余り、7で割ると4余...
-
おしどり遊び(テイトの飛び石...
-
至急!!二次関数について aは...
-
2進数のバイアス表現について
-
x.>0ときγ(x)が最小値となるxの...
-
Xの二次関数 y=x ²ーmx+m(mは...
-
正の約数の個数が20個である最...
-
数学2です x>0のとき、x + 16/(...
-
n!が10の40乗で割り切れるとき...
-
最小値のルートについて。
-
y=x^xの最小値
-
ある数字を割り切れる最小の数...
-
min{a,b,c}って何?
おすすめ情報