  |
はてなキーワード: 合成数とは
2. モジュラスの計算: N = p * q
3. オイラーのトーシェント関数: φ(N) = (p-1)(q-1) を計算する。
4. 公開鍵と秘密鍵の生成: 公開鍵は (N, e) であり、e は gcd(e, φ(N)) = 1 を満たす整数である。秘密鍵は d であり、d * e ≡ 1 (mod φ(N)) を満たす。
RSA暗号の安全性は、合成数 N の素因数分解が計算的に困難であることに依存している。具体的には、次の問題が考えられる：
N = p * q
ショアのアルゴリズムは、量子コンピュータ上で動作する効率的な素因数分解アルゴリズムである。以下にその主要なステップを示す。
任意の整数 a を選択し、N に対して次の条件を満たすことを確認する：
整数 a の順序 r を求める。順序とは、次の条件を満たす最小の整数である：
a^r ≡ 1 (mod N)
量子フーリエ変換は、状態ベクトルを重ね合わせて次のように表現される：
|x⟩ = Σ(k=0 to N-1) |k⟩
ここで、量子フーリエ変換を適用することで周期性に関する情報が得られる。具体的には、
QFT |x⟩ = (1/√N) Σ(j=0 to N-1) Σ(k=0 to N-1) e^(2πi jk / N) |j⟩
得られた状態から測定を行うことで周期情報が得られる。この周期情報を用いて次の式を考える：
x = a^(r/2) - 1
y = a^(r/2) + 1
これらが非自明な因子である場合、p と q を次のように計算できる：
p = gcd(x, N)
q = gcd(y, N)
ショアのアルゴリズムは確率的であり、成功率は高いものの100%ではない。そのため、誤り訂正技術や複数回実行することで成功確率を向上させる必要がある。
RSA暗号は、代数的構造、特に合同算術および整数環における準同型写像を用いた公開鍵暗号である。
RSAの安全性は、環の自己同型写像の一方向性と、有限生成群の元の分解が困難であることに基づいている。
この暗号方式は整数環 Z/NZ（N = p・q）上の準同型写像の一方向性を活用する。
まず、RSAにおける鍵生成は、代数的に以下のように構築される：
互いに素な大きな素数 p および q を選び、合成数 N = p・q を作成する。
これにより、商環 Z/NZ が定義される。ここで、N はRSAにおける「モジュラス」として機能する。
この商環は、全体として単位的な環であり、RSA暗号の計算基盤となる。
オイラーのトーシェント関数 φ(N) を次のように計算する：
φ(N) = (p - 1)(q - 1)
これは環 Z/NZ の単数群 (Z/NZ)* の位数を表し、RSAの準同型構造における指数の計算に用いられる。
単数群 (Z/NZ)* は、φ(N) を位数とする巡回群であり、一般に生成元 g ∈ (Z/NZ)* を持つ。
RSAでは、この群の生成元から得られる公開指数 e は、φ(N) と互いに素な整数として選ばれる。公開指数 e はRSAの「公開鍵指数」となる。
e・d ≡ 1 (mod φ(N))
これは、e に対する逆元 d の存在を保証し、秘密指数として機能する。ここで d はユークリッド互除法により効率的に求められる。
以上により、公開鍵 (N, e) と秘密鍵 (N, d) が生成される。これらの鍵は、合同算術と商環上の準同型写像によって定義される。
RSA暗号は、モジュラー演算によるべき乗写像を使用した暗号化および復号過程である。この操作は、(Z/NZ)* 上の自己同型写像に基づいている。
任意のメッセージ M ∈ Z/NZ に対し、公開鍵 (N, e) を用いて次の準同型写像を作用させる：
C = σ(M) = M^e (mod N)
ここで σ: M → M^e は (Z/NZ)* の自己同型写像として作用し、得られた C は暗号文となる。
この写像はモジュラ指数写像として同型写像であるが、一方向的であるため暗号化に適している。
暗号文 C を受け取った受信者は、秘密指数 d を用いて復号を行う。具体的には次のように計算する：
M = C^d (mod N) = (M^e)^d (mod N) = M^(e・d) (mod N)
ここで e・d ≡ 1 (mod φ(N)) であるため、e・d = kφ(N) + 1（整数 k）と表すことができ、したがって
M^(e・d) = M^(kφ(N) + 1) = (M^(φ(N)))^k・M ≡ 1^k・M ≡ M (mod N)
により、元のメッセージ M を復元することができる。ここでオイラーの定理に基づき、(M^(φ(N))) ≡ 1 (mod N) が成り立つため、この復号化が成立する。
RSA暗号は、Z/NZ の構成において N = p・q の因数分解が困難であることを仮定する。
合成数 N の素因数分解問題は、現在の計算アルゴリズムにおいて指数時間に近い計算量が必要であり、代数的には解読が非常に難しい問題であるとされる。
RSA暗号における暗号化は群の自己同型写像によって構成されるが、逆写像を求めることは一般に困難である。
これはRSAの一方向性を保証し、現実的に解読不可能な構造を形成している。
RSA暗号の解読は逆写像としてのべき乗の逆操作を計算することに相当し、これを効率的に解決する手段が存在しないことが安全性の根拠となる。
RSA暗号の構造は合同算術に基づく準同型性を有し、M → M^e (mod N) というモジュラ指数写像によりメッセージ空間上の一対一対応を実現する。
この準同型性により計算効率が保証されつつも一方向性を持ち、安全な暗号化が可能である。
以上より、RSA暗号は合同算術、準同型写像、群の生成元と逆元の難解さに基づく暗号であり計算量理論と抽象代数からその安全性が保証されている。
RSA暗号の解読可能性は準同型写像の逆像を効率的に求める方法が存在しないことに基づいており数学的にはこの逆像問題の困難性がRSA安全性を支えているといえる。
m + n = 2xなので、mとnは両方とも奇数 or 両方とも偶数。
m = n = 2のときはx + y = 2を満たす素数x, yは存在しないので不適。したがって、m, nはともに奇数。
x - y = nが奇数なので、xとyは一方が奇数でもう一方が偶数。x = 2だと、nが素数にならないので、y = 2。
よって、
(n, x, m) = (x - 2, x, x + 2)
がすべて素数となるxを求めればよい。
x = 5はこの例である。これ以外に解が無い事を示す。x＜5のときはx - 2, x, x + 2がすべて素数となるxは無い。
2 ≡ -1 (mod 3)より、x - 2, x, x + 2の1つは必ず3の倍数になる。したがってx＞5のとき、x - 2, x, x + 2の少なくとも1つは必ず合成数になる。
以上から、求める解は
(x, y, m, n) = (5, 2, 7, 3)
のみ。
https://twitter.com/mathmatsuri
問4
n=6, 8, 10, …, 78, 80の38通りなのですべて書き出せば解けるんだろうが、いかに省エネできるか考えながら進めていきたい。まずは実験しないと始まらない。
小さいnから考えるとパターンが少なすぎるので、大きいnから考えてみる。
n=80のとき(3, 77) (5, 75) (7, 73) (9, 71) (11, 69)…の中から素数のペアを探していけばよい。
nによらず同じように書き出していくことを考えると、まずは素数のリストがあった方がいい。77まででよい。また2は不要。
3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73
n/2よりも小さい素数より、n/2よりも大きい素数の方が多い。計算の回数を減らすために上から順番にnから引き算して素数が残るかどうか判定する。
素数が残る: 73, 67, 61, 43
合成数が残る: 71, 59, 53, 47, 41
pとqがともに素数となる組は(73, 7) (67, 13) (61, 19) (43, 37)とこれらを逆にした8通り。
よってP(80)=8/40=1/5
次、n=78に対して素数リストの上から順番に引き算していく。n/2=39まで。
素数が残る：73, 71, 67, 61, 59, 47, 41
合成数が残る: 53, 43
pとqがともに素数となる組は(73, 5) (71, 7) (67, 11) (61, 17) (59, 19) (47, 31) (41, 37)とこれらを逆にした14通り。よってP(78)=14/39
素数が残るパターンがずいぶん多かった。ところで求めるのはP(n)の最小値。今後分母は減っていくので、組み合わせの数が今のところの最小値の8以上になることが分かった時点でそれ以上計算する意味はなくなる。つまりn/2より大きいpが4つ見つかったらその時点で終了してよい。n/2が素数の時は別で考える必要があるので出てきたら考える。あと合成数が残るパターンは書き残さなくてもよい。
n=76で同様の操作を。
素数が残る：73, 71, 59, 53 ここで終了
n=74
71, 67, 61, 43 ここで終了
n=72
67, 61, 59, 53 終了
n=70のとき67, 59, 53, 47 終了
n=68のとき61, 37の2つだけ。つまりp, qが両方とも素数になるのは(61, 7) (37, 31)とその逆の4通り。
以後はn/2より大きいpが2つ見つかったらその時点で終了してよい。
n=66のとき61, 59 終了
n=62のとき59, 43 終了
n=60のとき53, 47 終了
n=58のとき53, 47 終了
n=56のとき53, 43 終了
n=54のとき47, 43 終了
n=52のとき47, 41 終了
n=50のとき47, 43 終了
n=48のとき41, 37 終了
n=46のとき43, 41 終了
n=44のとき41, 37 終了
n=40のとき37, 29 終了
n=38のとき31, 19(=n/2) p, qが両方とも素数になるのは(31, 7) (19, 19) (7, 31)の3通りなのでP(38)=3/19
P(68)=2/17=3/25.5なのでP(38)>P(68)
n=32のとき29, 19 終了
ここから先はn/2より大きいpが1つ見つかった時点でP(n)=2/(16以下)がP(68)=2/17を超える。
n=22のとき19 終了
n=18のとき13 終了
n=16のとき13 終了
n=8のとき5 終了
n=6のとき(p,q)=(3,3)のみ P(6)=1/3=2/6>2/17=P(68)
-----------------------------------------------------------------
新幹線乗ってる間暇だったから中学高校でやってた素数について考えたわけ
そのときさ、「pがp未満かつ1でない全ての自然数に対して割り切れない」って考えたんだけど
「pがp未満の全ての素数に対して割り切れない」って同じじゃねーかなみたいなことふと思ったの
んで同値であることを証明しようと思って、んでたぶん最初の命題から次の命題を証明するのは簡単じゃん
ｐ未満の全ての素数も自然数なんだから自然数で割り切れないんだったら素数でも割り切れないじゃん
でも二番目の命題から一番目の命題のやつだとなんとなく背理法でしかわかんないのね
pがp未満の全ての素数に対して割り切れないとき、pがp未満の1以外の自然数で割り切れるとすると
その自然数がもし素数なら、全ての素数に対して割り切れないことと矛盾するじゃん
この場合素数で割り切れることになってやっぱり全ての素数に対して割り切れないことと矛盾するじゃん
だからp未満の全ての素数で割り切れないならやっぱり1以外の全ての自然数でも割り切れないんじゃね？
ってなったのね。間違ってたらすんまそん
「1以外の全ての自然数で割り切れない」ことと「全ての素数で割り切れない」ことが一緒になるって普通におかしくね？
どう見ても自然数と素数って定義違うし集合も違うのにこのことが同じになったらおかしいじゃん
命題の使い方間違ってそう
