ニコニコ大百科

こんなためになる記事もあるのか

褒めておこう

なるほど、まったくわからん

高校が普通科でなく数Ⅰしかやってない自分がこれなら親切に説明あるからと挑戦してみたけど、小数点以下余りが膨大に出てあきらめた

誰が書いたんだ。でてこい、賞賛する

144÷35=4あまり4
4÷35=0あまり4

これがわからなくて３０分近く悩んだのは俺ぐらいか…

電卓で余りを出す方法
　(割られる数)-(割る数×割り算の結果の整数部分)=余り

これってあってるかな？

なるほど、よくわからん

非常に分かりやすいです、どうもありがとうございます

>>5
google先生なら
割られる数 mod 割る数
で余りを教えてくれる

>>8
マジだ、すげー

離散勉強している俺にとっては良記事
かなり分り易く書かれているよ
評価します

>>10
俺もだ。
情報系だからここら辺のことは触りでもいいから知らなきゃならんのだよねぇ。

>>5
プログラミング言語の大半は余りを求める演算子があるからそれを利用すると幸せになれると思う。

ゴルゴ１３で
「数百桁の数字の２乗を計算するのは比較的簡単だが
数百桁の数字の平方根を計算するのはスパコンでも宇宙の終焉までかかる。
その特性を使えば簡単に作れて解読は不可能な究極の暗号を作れる！」
という話があって、この理論が本当にあって使われてるのかなと思ってたけど、このＲＳＡ暗号が元ネタだったんだろうな。

>>13
多分RSAの事だろうけど、素因数分解がどうして平方根にすりかわったのか、興味深い
(一応マジレスしておくと、平方根求めるのは桁数大きくても簡単、素因数分解ならその通りなんだけど)

そしてP≠NPとかどうのこうの

これで興味持った奴はサイモンシンの暗号解読って本読むといいよ
暗号製作者と暗号解読者の戦いの歴史を知れる

「RSA フェルマー」でググったら、他のサイトを差し置いて検索順位1位でニコニコ大百科が出てきてワロタｗ

レポートの参考にします。マジサンクス。

おお、良記事。
たまにこういう専門的なのにわかりやすい記事があるから嬉しい。

電子署名の時は鍵の公開と秘密を逆にするんだよな
昔勉強した時に混乱したわ。（RSA暗号に限らない話だから蛇足だけど）

ちょっと別の記事書くために色々ググってたんだが良い記事だなおい
記事主がプレミアム退会しちゃってるっぽいのが惜しまれる

鍵錬成の手順5
>(e,n)を公開鍵とし、(d,n)を秘密鍵とする。
って
>(e,n)を公開鍵とし、(d,p,q)を秘密鍵とする
の誤り？？nは公開鍵だし。

>>20
復号の方法をよく見てみよう
p, q, dはいずれも秘密にしなければいけない情報だが、復号の際に必要になる情報(=秘密鍵)はdとnだけ

まあ、nはすでに公開しているから秘密鍵はdだけと考えることもできるけど、どちらにしろp, qはばれるとまずい(dがわかってしまうため)情報ではあるが、そもそもp, qは鍵生成の過程で一時的に必要になるだけであって、保管しておく必要自体ないわけだ

記事の　p = 5,q = 7,n = 35,e = 5,d = 5　のところ
中途半端にスペース入れてあって見づらいと思います。
入れるなら　p = 5 , q = 7 , n = 35 , e = 5 , d = 5　で良いのでは。

p = 5, q = 7, n = 35, e = 5, d = 5　や
p=5, q=7, n=35, e=5, d=5　のほうが自然かな。
ともかく、イコールの前後に入れて、コンマの後に入れないのは変に思える。

くっ

素数3つだと、ダメなのは何故？別に説明見る限りでは特に問題なさそうだし、そっちの方が安全性も上がりそうだけど…

>>25
実際に計算してみれば確かに素数３つでもよいが、２つに定着したのは安全さのためじゃないかと思う
なぜなら、３００桁の合成数の場合、素数２つの積である時、小さい方の因数は最大１５０桁なのに対し、素数３つだと一番小さい因数は最大１００桁しかない
つまり、素数２つの積の方が素因数分解されにくいということによるとおもう

pq を法としたただの合同算術って考えるとすんなり腑に落ちてしまう。(p-1)(q-1)乗が1になるのもちょっと数学やった身だとああそうだよねって思えるようになる。

>>13 >>14
数百桁の数に平方根記号をかぶせたものから素因数の二乗（専門的には平方因子という）を括り出す、中高でおなじみのアレなら、素因数分解を兼ねてるから、当たらずと言えども遠からずって感じ……？　小数で計算するのは楽勝だもんね

RSA暗号は二つの数が必要で準指数関数的時間で解けるアルゴリズムがある
楕円曲線暗号は一つの数でよくてまだ指数関数時間アルゴリズムしか見つかっていない
なので同じ強度にするのに必要とされる桁数が楕円曲線暗号の方が大幅に少なく済む

https://www.youtube.com/watch?app=desktop&v=kvC55N4k9ng

補足資料にどうぞ

>>20, >>21
(p, n), (q, n), (p, q), (d, n) いずれでも情報としては足りてますが、実運用上は計算時間の削減のため (n, d, p, q, d mod (p-1), d mod (q-1), q^{-1} mod p) みたいなとりあえず色々入れとけみたいなデータ構造になってます
>>25, >>26
「最小の素因数の大きさ」によって計算時間が決まる素因数分解アルゴリズムがあるので、それへの耐性は大きい方から 2 番目の素数の大きさで決まります。なので同じ大きさの素数 2 個の方がよいですし、どうしても素数 3 個を使うなら 3 × (150 桁の素数) × (150 桁の素数) とするのが多分最善でしょう (一番小さい素数の大きさは適当でもいいです)