0Pricing
Cryptology Academy · レッスン

素数と素因数分解

素数が公開鍵暗号の基盤である理由を学びます。

「素数と素因数分解」はCoddyKit上の無料Cryptology Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCryptology Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Cryptology Academyコースには全4レッスンが含まれています。

ようこそ

素数は1と自分自身以外に割り切れる数を持ちません。素数は乗法における原子のようなもので、RSA、Diffie-Hellman、その他多くの暗号システムの基盤です。

定義と例

素数：2、3、5、7、11、13、17、19、23、29、...。ある数が素数であるとは、正の約数が1と自分自身だけであることです。1は、定義上、素数ではありません。

算術の基本定理

1より大きいすべての整数は、素数の積に、順序を除いてただ1通りに分解できます。60 = 2² × 3 × 5です。この一意性が、素因数分解に基づく暗号を成立させています。

試し割り法

def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True √nまで調べれば十分です。√n未満に因数が見つからなければ、nは素数です。

エラトステネスのふるい

N以下のすべての素数を見つけるには、まず2..Nの数のリストを用意します。2の倍数、次に3の倍数、5の倍数というように消していきます。最後に残った数が素数です。計算量はO(N log log N)です。

素数判定：Miller-Rabin法

大きな数（2048ビット）では、試し割り法は遅すぎます。Miller-Rabin法は確率的な判定法です。40回実行すると、誤判定の確率は4^(-40)未満になります。

整数の素因数分解

n = p × qが与えられたとき、pとqを見つける問題が整数の素因数分解問題です。nが2048ビットの場合、現在知られている最良のアルゴリズムでも2^112回の演算が必要で、現時点では実行困難です。

RSAが2つの大きな素数を使う理由

RSAの法n = p × qです。nは分かっていてもpとqが分からなければ、秘密鍵の計算は困難です。安全性は完全に、nの素因数分解の困難さに依存しています。

大きな素数の生成

from sympy import randprime p = randprime(2**1023, 2**1024) # random 1024-bit prime 手順：ランダムな奇数を生成し、Miller-Rabin法で判定して、素数になるまで繰り返します。

安全素数と強い素数

安全素数pとは、qも素数であるp = 2q+1の形の素数です。安全素数は、DHに対する特定の攻撃に耐性があります。RSAでは、Pollardのp-1攻撃を防ぐために、強い素数を使うことがあります。

素数間隔と無限性

ユークリッドは紀元前300年に、素数が無限に存在することを証明しました。双子素数予想（pとp+2がともに素数となる組が無限に存在するという予想）は、今も証明されていません。暗号に使う素数が尽きることはありません。

確認問題

RSAでは、なぜ大きな素数を使うのですか？

まとめ

素数と素因数分解について理解できました。次は、RSAの前に必要となる最後の数学的道具として、オイラーのトーシェント関数とGCDを学びます。

よくある質問

「素数と素因数分解」レッスンは無料ですか？

はい。「素数と素因数分解」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Cryptology Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Cryptology Academyコースには全4レッスンが含まれています。

「素数と素因数分解」で何を学びますか？

素数が公開鍵暗号の基盤である理由を学びます。 ブラウザで直接実行するハンズオンコードでCryptology Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Cryptology Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCryptology Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「素数と素因数分解」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCryptology Academyレッスンでコードを書いて実行できますか？

はい。すべてのCryptology Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 2進数と16進数の基礎
  2. 剰余算の基礎
  3. 素数と素因数分解
  4. GCD、Eulerのトーシェント関数と数論入門
← Cryptology Academyに戻る