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
●質問のご真意を読みかねるところもある気がするので、「自信なし」です。
ありがとうございます。簡単に言えば最大公約数をもとめるものだったんですね・・・
暗号化理論という分野の問題だったのですが、授業でやったときは、
gcd(x,y)=sa+tb (∃s,t)
に分解するようなa,bがある。
という説明をうけたものですから、「互いに素」という概念に気づきませんでした。
あとは大丈夫そうです。
ありがとうございました
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・【お題】絵本のタイトル
- ・【大喜利】世界最古のコンビニについて知ってる事を教えてください【投稿~10/10(木)】
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
全員と同じグループを経験でき...
-
2進数のバイアス表現について
-
次の問題を解いてください。 実...
-
至急!!二次関数について aは...
-
図形問題、最小値
-
座標平面上において、放物線y=x...
-
中学受験用の小5算数の問題です
-
最小値が-2でグラフは2点(0、0)...
-
3次元での点群に対する最小二...
-
正の約数の個数が20個である最...
-
2次関数の問題の場合分けで理解...
-
1/x+1/y+2/z=1を満たす自然数解
-
おしどり遊び(テイトの飛び石...
-
ユークリッドの互徐法
-
ある数字を割り切れる最小の数...
-
数学です この問題わかるかた教...
-
EXCEL ドラッグしたセル...
-
数学です至急!! a<0とする。 ...
-
数学の問題
-
1/x+1/y≦1/2 , 2<x,2<yのとき、...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
全員と同じグループを経験でき...
-
至急!!二次関数について aは...
-
2進数のバイアス表現について
-
数学Aの確率
-
【放物線の問題】
-
y=x^xの最小値
-
数学の問題がわからず困ってお...
-
数学2です x>0のとき、x + 16/(...
-
中学受験用の小5算数の問題です
-
3次元での点群に対する最小二...
-
おしどり遊び(テイトの飛び石...
-
次の問題を解いてください。 実...
-
x.>0ときγ(x)が最小値となるxの...
-
高校数学1の問題集に、2次関数...
-
3で割ると2余り、7で割ると4余...
-
Xの二次関数 y=x ²ーmx+m(mは...
-
0は公約数?
-
1/x+1/y≦1/2 , 2<x,2<yのとき、...
-
問題文は解答欄に載せます。 四...
-
最小値が-2でグラフは2点(0、0)...
おすすめ情報