はやわかり RSA

山本和彦
IIJ 技術研究所
作成：2001年11月19日
改訂：2006年8月3日

RSA の歴史

人類は 2000 年もの間、共有鍵暗号という種類の暗号を用いてきました。共有鍵暗号とは、暗号化するときと復号化するときに使う鍵が同一の暗号を言います。Alice と Bob が共有鍵暗号を使って通信する際には、あらかじめ鍵を共有しなければなりません。

これに対し、「暗号化に使う鍵と復号化に使う鍵が異なれば、あらかじめ鍵を共有する必要はなくなるはずだ」という概念が提案されました。現在これは、公開鍵暗号と呼ばれています。提案者は Whitfield Diffie と Martin Hellman で、発表は 1976 年のことです。

この概念が示された論文 "Multiuser Cryptographic Techniques"[1] を、MIT の Ronald Rivest、Adi Shamir、Len Adleman も入手しました。しかし、いくら考えてもそんな暗号は作成できず、そもそも概念自体が矛盾しているように感じられました。そんな暗号は実現できないことを証明しようと試みたほどだったようです。

数ヵ月後、Diffie と Hellman は、今では Diffie-Hellman 鍵交換方式と呼ばれる手法を、論文 "New Directions in Cryptography"[2] で発表しました。この Diffie-Hellman 鍵交換方式は、狭い意味では公開鍵暗号ではありません。しかし、Alice と Bob が直接会うことなく秘密を共有できることは証明されました。このことは、Rivest らに公開鍵暗号が必ず実現できるという確信を与えたのです。

1977年、ついに Rivest らは初の公開鍵暗号の開発に成功しました。この暗号は、開発者の名にちなんで RSA と呼ばれています。RSA は現在も有力な公開鍵暗号の 1 つであり、2000年9月に特許が切れて、誰でも自由に利用できるようになりました。

暗号化と復号化の方式

RSA の公開鍵は、正数 n と e です。秘密鍵は、正数 n と d です。d は、ある計算により n と e から導かれます。

RSA では、1 〜 n - 1 の正数を暗号化できます。n 以上の数は、n (あるいは、n より小さい数)で分割し、それぞれを暗号化します。

ここで Bob が Alice へ暗号文を送ることを考えましょう。Alice は Alice の公開鍵 {n, e} を公開します。Bob は、これをあらかじめ入手します。

Bob が Alice 宛の暗号文を作成する手順は、以下の通りです。

C = M^e (mod n)

ここで、M は平文(message)を、C は暗号文(cipher)を表します。両者は 1 〜 n - 1 の正数です。`^' は巾乗を表します。たとえば、M^e は M の e 乗を意味します。また、(mod n) とは n で割った余りを表しています。

C が計算できたら、Bob は C を Alice に送ります。

Alice が暗号文を復号化するには、以下のように計算します。

M = C^d (mod n)

暗号化と復号化の式をみれば、1 〜 n - 1 を 1 〜 n - 1 へ 1 対 1 に射影していることが分かります。有限の空間で、行って帰って来ると同じ値になるのですから、1 対 1 の関係にある訳です。

式が対称なので、暗号化と復号化の関係を入れ替えて利用することもできます。すなわち RSA では、上記のように公開鍵で暗号化し、秘密鍵で復号化できますし、逆に秘密鍵で暗号化し、公開鍵で復号化することもできます。前者は暗号文、後者は電子署名として利用されます。

一般に、e は小さい正数、d は大きい正数となります。ですから、e を使った計算(暗号化と署名の検証)は、d を使った計算(復号化と署名の作成)よりも高速です。

暗号化と復号化の例

たとえば、公開鍵を {377, 11}、これから導いた秘密鍵を {377, 23} としましょう。377 は 256 よりも大きいので、1 バイト(0 〜 255) を十分に暗号化できる能力があります。ですから、この場合は平文を 1 バイトずつに区切って暗号化すればよいことになります。

細かいことですが、暗号化の式から分かるように、0 や 1 は暗号化してもそれ自身となり特異点です。よって 0 と 1 は、それぞれ 256 と 257 に変換するなどの工夫が必要です。

ここで文字 'a' を暗号化することを考えましょう。'a' の ASCII コードは 97 です。暗号化は以下のようになります。

C = 97^11 (mod 377)

式を見ると簡単そうですが、実際に計算すると 97^11 は大きな数になります。通常、n は 1024 ビット程度の大きさですから、単純に計算するのではメモリがいくらあっても足りません。

そこで、「大きくなる前に適宜割っていっても、最終的な余りは変わらない」という性質を使って計算します。式で表わすと以下のようになります。(正確を期すために、しつこく括弧を書きます。)

{a * b} (mod n) = {(a (mod n)) * (b (mod n))} (mod n)  ＃1

しかし、97 (mod 377) を 11 回かけて、最後に 377 で割ればよいと思ってはいけません。97 (mod 377) は 97 なので、意味がありません。この性質を巧みに利用するのが、乗数 e (あるいは d) を 2 の巾数に分解する手法です。つまり、以下のように考えます。

97^11 = 97^(1 + 2 + 8) = 97 * 97^2 * 97^8

それぞれの (mod 377) を計算してみましょう。

97^2 = 9409 = 361 (mod 377)
97^4 = {97^2}^2 = 361^2 = 130321 = 256 (mod 377)
97^8 = {97^4}^2 = 256^2 = 65536 = 315 (mod 377)

よって、97 を暗号化すると、以下のように 89 になります。

97^11 = 97 * 97^2 * 97^8
      = 97 * 361 * 315
      = 35017 * 315
      = 333 * 315
      = 104895
      = 89 (mod 377)

練習として 89 を復号化し 97 に戻るか調べて下さい。

89^23 = 97 (mod 377)

鍵の生成

RSA では、以下の手順で公開鍵と秘密鍵を生成します。まず、大きな素数 p と q を乱数から生成します(p と q は、異なる素数です)。よく耳にする「1024 ビットの鍵」を生成するには、512 ビット程度の素数を 2 つ生成することになります。(こう言うと簡単に聞こえるかもしれませんが、発生させた乱数が素数であるか判定するのは、実は大変難しい作業です。)

p と q を掛け合わせた正数が n となります。

n = p * q

ここで、p - 1 と q - 1 の最小公倍数をとります。これを L と呼びましょう。最小公倍数を計算する関数を lcm() とすると、以下のように表わせます。

L = lcm(p - 1, q - 1)

ここで、L と「互いに素」で、L より小さい値 e を選びます。(e に 3 を選ぶと弱いことが分っているので、3 を使ってはいけません。PGP 2 は、通常 e に 11 を選びます。 pgpdumpなどを使って、自分の PGP の RSA 公開鍵を調べて下さい。e が 11 になっていませんか？e に第4のフェルマー数 65537 を選ぶのも一般的です。)

次に、以下の式を満たす d を探します。

ed = 1 (mod L)

d は未知数なので、y とおきます。するとこれは、

Lx + ey = 1

となる負数 x と 正数 y を探す問題と等価です。そのときの y が d となります。この理由は後で説明します。d を探すには「拡張ユークリッドの互除法」が利用できます。これも後述します。

上記の例、すなわち

n = 377、e = 11、d = 23

は、次のようにして計算されました。

まず、p に 13、q に 29 を選びました。ですから、

p = 13
q = 29
n = p * q = 13 * 29 = 377

となります。ここで L は、

L = lcm(p - 1, q - 1)
  = lcm(12, 28)
  = 84

となります。d を算出するためには、

84x + 11y = 1

を満たす x と y (y > 0) を見付けなければなりません。その y が、d となります。

この算出方法を理解することを、当面の課題とします。

時計算数

証明は省略しますが、a と b が「互いに素」なら、

by = 1 (mod a)

を満たす y が必ず存在します。

ここで、by を a で割った余りが 1 なので、by を a で割った商を x' とすると、

by = ax' + 1

が成り立ちます。x' を -x と置き換えると、以下のように書き換えられます。

ax + by = 1

すなわち、正数 a と b が互いに素であれば、

ax + by = 1

を満たす、整数 x と y が存在することになります。

我々が求めたいのは、

ed = 1 (mod L)

でした。e と L は互いに素であるので、d は必ず存在します。e と L は既知なのでそのまま、d は未知なので y とおきましょう。すると、以下の式を満たす整数 x と y が存在し、その y が求める d となります。

Lx + ey = 1

この式を変形すると以下のようになります。

y = -(L/e)x + 1/e

この直線が x も y も整数になるところを見付けることになります。解の存在は保証されていますので、1 つは解があることになります。すると、x 方向に e (あるいは -e) 、y 方向に -L (あるいは L) 動かすと、そこも整数の解になることは明らかです。という訳で、この式を満たす整数 x と y は無数にあります。

もし、拡張ユークリッドの互除法を用いて計算した結果、d が負数になった場合、d に L を足せば最小の正数を算出できます。

ユークリッドの互除法

「拡張ユークリッドの互除法」を学ぶには、まず「ユークリッドの互除法」を知る必要があります。

ユークリッドの互除法は、2 つの正数の最大公約数を算出する方式です。これは、小さい方の数の桁数の 5 倍の手間で計算が終わる高速な手法であるため、よく用いられています。

たとえば、RSA の鍵の生成の際に、素数 p と q を選ぶ必要があります。そこで任意に選んだ正数 p と q が素数であるか判定するのに、たくさんのテストを実施します。その 1 つとして、ユークリッドの互除法が使われます。p と q が素数であれば、「互いに素」であるはずです。ですから、p と q の最大公約数は 1 にならないといけません。最大公約数が 1 になっても、互いに素であることが分かるだけで、素数であることを保証できる訳ではありません。しかし、この方法で明らかに素数ではない数をすばやく除去できます。

中学校で、素因数分解による最大公約数の算出を習った人も多いと思います。この方法にはいくつかの欠点があります。1 つは、コンピュータには素因数分解するという基本的な演算がないので、素因数分解のプログラムを作らなければならないことです。もう 1 つは、大きな数の素因数分解はとても困難であり、実際問題として計算できないことです。

ユークリッドの互除法は、「大きい方の数から小さい方の数を引く」という作業を繰り返すだけです。これなら、コンピュータで容易に実装できますし、桁数が大きくなっても計算可能です。

引き算するだけで本当に最大公約数が求まるのかと疑問に思う人もいるでしょう。では、実際に 30 と 15 の最大公約数を求めてみましょう。30 から 15 を引いて下さい。

30 - 15 = 15

ほーら、最大公約数 15 が求められました。騙されたような気になっているかもしれませんが、本当の話です。

この理由は以下のようになります。正数 a と b (a > b) とし、その最大公約数を G とすると、

a = GA
b = GB

を満たす、正数 A と B が存在します。a と b を引くと

a - b = G(A - B)

となり、G は残ります。A - B が 1 に等しくなれば、G が求められます。

一般的には、複数回の引き算を実行する必要があります。手順は以下のようになります。

[ユークリッドの互除法] (i) a から b を引きます。この結果を c とします。c が 0 となる場合に繰り返しを止めます。このときの b が答です。そうでなく、c が b よりも大きい場合、c を a に代入し、(i) に戻ります。c が b 以下の場合、b を a、c を b に代入し、(i) に戻ります。

実際にやってみましょう。210 と 66 の最大公約数を求める手順を以下に示します。

  a    b     c
210 - 66 = 144
144 - 66 =  78
 78 - 66 =  12
 66 - 12 =  54
 54 - 12 =  42
 42 - 12 =  30
 30 - 12 =  18
 18 - 12 =   6
 12 -  6 =   6
  6 -  6 =   0

このように、210 と 66 の最大公約数 6 が算出できました。

これまでの内容に感銘を受けた人もいるかもしれませんが、実はまだ改良の余地があります。引いた結果(c)が、引く数(b)よりも小さくなるまで繰り返し引くということは、割った余りを求めていることに他なりません。よって、以下のように高速化できます。

[ユークリッドの互除法(改良版)] (ii) a を b で割り余りを c とします。c が 0 となる場合に繰り返しを止めます。このときの b が答です。そうでなければ、b を a、c を b に代入し、(ii) に戻ります。

上記の例は、以下のように計算量が減ります。(`%' は、余りを計算する演算子とします。)

  a    b    c
210 % 66 = 12
 66 % 12 =  6
 12 %  6 =  0

拡張ユークリッドの互除法

最大公約数を計算する関数を gcd() としましょう。ユークリッドの互除法は、正数 a と b に対し、

ax + by = gcd(a, b)

となる整数 x と y が存在していることを意味しています。

ここで、時計算数の話を思い出して下さい。a と b が互いに素であれば、gcd(a, b) = 1 ですから、

ax + by = 1

となり、これを満たす x と y が存在する根拠にもなっています。

拡張ユークリッドの互除法は、a と b (a > b) の最大公約数を求めるついでに、x と y も決定してしまう方法です。以下のような手順を踏みます。

補助式を用意します。

ax1 + by1 = z1
ax2 + by2 = z2

初期値として以下のように代入します。(`←' は代入を表わします。)

(x1, y1, z1) ← (1, 0, a)
(x2, y2, z2) ← (0, 1, b)

以下を z2 が 0 になるまで繰り返します。そのときの (x1, y1, z1) が、求めたい (x, y, gcd(a, b)) となります。

q ← z1 を z2 で割った商
(x3, y3, z3) ← (x1, y1, z1) - q * (x2, y2, z2)
(x1, y1, z1) ← (x2, y2, z2)
(x2, y2, z2) ← (x3, y3, z3)

d の求め方

拡張ユークリッドの互除法を使って、懸案だった

84x + 11y = 1

を満たす整数 x と y (y > 0) を探してみましょう。その y が求める d です。

L > e ですから、a を L、b を e とおきます。

(x1, y1, z1) ← (1, 0, L)
(x2, y2, z2) ← (0, 1, e)

ここから、拡張ユークリッドの互除法の繰り返し部分を計算すると以下のようになります。

a  *   x  +  b *    y  =  z
----------------------------------
84 *   1  + 11 *    0  = 84
84 *   0  + 11 *    1  = 11
                            (q = 7)
84 *   1  + 11 *  (-7) =  7 
                            (q = 1)
84 * (-1) + 11 *    8  =  4 
                            (q = 1)
84 *   2  + 11 * (-15) =  3 
                            (q = 1)
84 * (-3) + 11 *   23  =  1   <= 答
                            (q = 3)
84 *  11  + 11 * (-84) =  0

よって、d = 23 という答が導けました。e と L は互いに素なので、最大公約数 z が 1 となっている点にも注意して下さい。

RSA の安全性の根拠

RSA が安全なのは、大きな正数の素因数分解はとても困難であるという事実に基づいています。

鍵を生成する人は、素数 p と q を選択し、それを掛け合わせてn を計算します。これは簡単な作業です。また、p と q から、 e と d を導けます。これも簡単な作業であることは説明しました。

公開鍵 {n, e} を入手した悪者が、秘密鍵 {n, d} を推測する方法を考えてみましょう。d を導くには、n を p と q へ素因数分解する必要があります。通常、n は 1024 ビット程度の正数です。これを 512 ビット程度の p と q へ素因数分解することになります。

この素因数分解のためには、まず 512 ビット程度の素数表を作り、それらで割りきれるか順に試します。

大きな正数はほどんどが合成数です。素数は砂漠の中のオアシス程しか存在しません。数学王ガウスは、正数 n 以下の素数の数を n / log(n) (底は e)に近いと予想しています。この式から、512 ビットの正数空間にある素数を算出すると、以下のようになります。

2^512 / log(2^512) = 2^512 / {512 * log(2)} ≒ 2^512 / 2^9 = 2^503

砂漠の中のオアシスといっても、途方もない数です。素数判定自体が難しく、ほどんどは合成数で役に立たず、しかも素数の数自体も巨大。そんな条件で素数表を作成することがいかに困難か理解できると思います。

しかし、「n を素因数分解しなくても d を求める方法が存在するか」という問題は、現在でも未解決です。RSA が安全であると信じられているのは、多くの人がよってたかって考えても、そのような方法がまだ見つかっていないからです。

RSA129

RSA の誕生は 1977 年のことですが、文献[3]から分かるように正式に発表されたのは 1978 年のことです。発表が遅れたのは、NSA(National Security Agency) の横やりが入ったためだと言われています。

その間に、Scientific American で "Mathmatical Games" というコラムを連載をしていた Martin Gardner が、RSA を紹介したいと Rivest に申し出ました。そのコラム[5]には、RSA の公開鍵と暗号文が懸賞問題として載りました。n が 10 進数 129 桁あることから、この問題は RSA129 という名で知られるようになりました。

RSA129 の公開鍵を以下に示します。

n = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
e = 9007

n は 2 進数にすると、429 ビットになります。

この公開鍵に対応する秘密鍵で作成された暗号文は以下の通りです。

C = 96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154

オリジナルの平文には、01 = 'A'、02 = 'B'、... というコードが使われています。

Rivest は、RSA129 の問題に 100 ドルの懸賞金を懸けました。最初に平文へ復号化できた人に、Rivest が 100 ドルを支払います。Rivest はこの暗号文を解読するために n を素因数分解するには、約 1015 年かかると予想しました。

また Rivest は、対応する秘密鍵を持っていることを証明するために、以下の電子署名も掲載しました。署名対象となる平文を M' とすると、署名 S は以下のように秘密鍵を使って暗号化して算出します。

S = M'^d (mod n)

M' を取り出すには、以下のように公開鍵で復号化します。

M' = S^e (mod n)

Rivest が掲載した署名は以下の通りでした。

S = 16717861150380844246015271389168398245436901032358311217835038446929062655448792237114490509578608655662496577974840004057020373

これを公開鍵で復号化すると以下のようになります。

M' = 06091819200019151222051800230914190015140500082114041805040004151212011819

これを上記のコード体系に従って文字に直すと、以下の文章が得られます。

FIRST SOLVER WINS ONE HUNDRED DOLLARS

17 年の間、誰もこの暗号文を解読できませんでした。1993年、Bellcore の Arjen Lenstra と MIT の Derek Atkins らは、この問題に挑戦するため素数探索のプログラムを作り、インターネットで配布しました。

最終的には、20 以上の国から約 600 名の参加があり、約 1600 台のコンピュータを 8 ヶ月間使った結果、大きな素数表ができあがりました。そしてその表を利用し、ついに n が素因数分解されました。

1994年4月26日、ニューヨークで祝賀会が催され、解が発表されました。翌日 Atkins は、sci.crypt などのニュースグループにその結果をアナウンスしました。

n は、以下のように素因数分解されました。

n = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
  = 3490529510847650949147849619903898133417764638493387843990820577 * 32769132993266709549961988190834461413177642967992942539798288533

この p と q から算出した d は以下の通りです。

d = 106698614368578024442868771328920154780709906633937862801226224496631063125911774470873340168597462306553968544513277109053606095

得られたこの秘密鍵を使い暗号文を復号化すると、以下のようになりました。

M = 200805001301070903002315180419000118050019172105011309190800151919090618010705

これを上記のコード体系から文章に直すと以下のようになります。

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

RSA129 は、n の大きさをどれくらいにすれば安全かという疑問に対する指標としてよく引き合いに出されます。現在のコンピュータの能力をもってすると、RSA129 のように n が 429 ビットでは解読される危険性があります。ですから、安全を期して 512 ビットの鍵は利用しない方がいいでしょう。

素因数分解は、n が 10 ビット増えると 2 倍時間がかかると言われています。単純に計算すると、1024 ビットを鍵を使えば、512 ビットの鍵よりも約 2^50 倍強力になります。

そこで、RSA の鍵を作成する際には、n に 1024 ビット以上の数を利用することをお勧めします。

鍵の衝突

世界には 60 億人とも言われる人が生活しています。この人達がそれぞれ RSA の鍵を作成するとします。このときに、すべての人が他の人とは異なる鍵を生成できないと、たいへん困ったことになります。

直感的には、同じ鍵が複数生成されてしまうことがありそうな気になります。しかし、このような鍵の衝突が起る確率は限りなく 0 です。

同じ鍵が生成されるということは、たまたま同じ p と q の組を選んでしまうということです。たとえば、512 ビットの素数空間から素数の組を取り出すときに、たまたま同じ組を選んでしまう確率はいくらかという問題になります。

この衝突の問題を理解するには、誕生日のパラドックスについて学ぶ必要があるでしょう。たとえば、ある場所に 30 名程度の人がいるとします。「その中で誕生日が一緒の人がいるか、いないか、どちらかに賭けろ」と言われたら、あなたはどちらに賭けますか？大抵の人は「いない」方にかけるでしょう。なんといっても、1 年は 365 日もあるのですから。

誕生日が衝突する確率は、衝突しない確率を 1 から引けば出てきます。1 名しかいない場合は衝突しません。2 名の場合は、最初の人の誕生日を避ければよいので、以下のようになります。

1 - 364/365

3 名の場合はこうです。

1 - 364/365 * 363/365

このような計算をしていき、確率が 0.5 を越える人数を計算すると、23 人となります。 つまり 23 以上人がいるなら、「いる」方に賭けた方が分がいいのです。

ここで、次の結論が導かれます。すなわち、「取り出す数が母数に近いと衝突する確率は高い」。365 と 23 は一桁しか違いません。これでは衝突してしまいます。

逆に「取り出す数より母数が圧倒的に大きければ、衝突する可能性は限りなく 0 に近い」とも言えます。世界人口 60 億は、2^33 程度の数です。これに対し、512 ビットの中にある素数の数は 2^503 です。比較するのが馬鹿らしいぐらい、母数の方が圧倒的に大きいのですから、衝突する確率はほとんど 0 です。

L について

RSA の最初の論文[3]では、L が以下のように積になっていました。

L = (p - 1)(q - 1)

論文[4]では、これまでの説明のように L が最小公倍数となっています。

L = lcm(p - 1, q - 1)

結論から先に言うと、前者は RSA が成り立つための十分条件、後者は必要十分条件となります。

L が異なれば一般に d も異なってきます。しかし、d を計算する際にどちらの L を使っても、RSA は成立します(暗号文を平文に戻せます)。

一般に、lcm(p - 1, q - 1) の方が、(p - 1)(q - 1) よりも小さいので、小さな d を算出できる可能性があります。すると、復号化の計算(C^d (mod n))が高速になるという利点があります。

p = 13, q = 29 の場合を考えてみましょう。e は 11 とします。

L に lcm(p - 1, q - 1) である 84 を選ぶと、上記のように d は 23 となります。

L に (p - 1)(q - 1) である 336 を選ぶと、d は 275 となります。

これは、n = 377、e = 11 の場合、d を 23 としても 275 としてもよい(同様に復号化できる)ことを意味しています。'a' (ASCII コード 97) の例に戻るなら、

89^23 = 97 (mod 377)
89^275 = 97 (mod 377)

となり、どちらでも復号化できています。

RSA の証明

RSA で、暗号文 C が平文 M に戻ることを証明しておきましょう。暗号化と復号化の計算式は、

C = M^e (mod n)
M = C^d (mod n)

ですから、＃1 を考慮しながら前者を後者に代入すると、

M = (M^e)^d (mod n)
  = M^(ed) (mod n)
  = M^(ed) (mod pq) ※0

となります。この式が成立する条件を考えます。

この式を変形すると、

M^(ed) - M = 0 (mod pq) 
M(M^(ed - 1) - 1) = 0 (mod pq)

となります。これは、左辺が pq で割りきれる、すなわち pq の倍数であることを意味しています。

ある数 X が pq の倍数となるには、p と q は素数ですから、「X が p の倍数、かつ X が q の倍数」である必要があります。

これを使って、上記を書直すと、

M(M^(ed - 1) - 1) = 0 (mod p) ※1

かつ

M(M^(ed - 1) - 1) = 0 (mod q) ※2

となります。

ここで、フェルマーの小定理を説明しましょう。フェルマーについては、最終定理(大定理)の方が有名でしょう。しかし、最終定理自体には実用性がほとんどないのに対し、小定理の方は実に役に立ちます。

[フェルマーの小定理] ある正数 a と素数 p があったとき、a^p - a は p で割りきれる。

式で表すと

a^p - a = 0 (mod p)

となります。

なんとすごい定理でしょうか。すべての素数は、この式を満たす性質を持っているのです。試しにやってみましょう。a = 10、p = 3 とすると、

10^3 - 10 = 1000 - 10 = 990

となり、確かに 3 で割りきれます。

ここで、フェルマーの小定理を以下のように変形します。

a(a^(p - 1) - 1) = 0 (mod p)

(mod p) の系において、p の倍数は 0 と同じ意味を持ちますから、a が p の倍数の場合は、両辺を a で割ってはいけません。それ以外の場合は、a で割っても構いません。すなわち、以下のことが言えます。

[フェルマーの小定理の変形] ある正数 a が素数 p の倍数でないとき(互いに素のとき)、以下の式が成り立つ。

a^(p - 1) - 1 = 0 (mod p) ※3

これで準備が整いました。※1 の成立条件を考えてみましょう。

(1) M が p の倍数であるとき：※1 が成り立つのは自明です。

(2) M が p の倍数でないとき：※1 の両辺を M で割れるので、

M^(ed - 1) - 1 = 0 (mod p)

が成り立つ条件を考えればよいことになります。これを ※3 と比較すると、ed - 1 が p - 1 の倍数、すなわち

ed - 1 = 0 (mod p - 1) ※4

が※1が成り立つための十分条件となります。証明は省きますが、この条件が必要である M も存在します。よって、任意の M に対し成り立つには、これが必要十分条件となります。

このことを言い換えると、

ed - 1 = k(p - 1)

を満たす k が存在するとき、かつそのときに限り、

(M^k)^(p - 1) - 1 = 0 (mod p)

が成り立つことが分かります。M と p は互いに素なので、M^k も p と互いに素であることに注意しましょう。

同様に、※2 が成り立つための必要十分条件は、

ed - 1 = 0 (mod q - 1) ※5

となります。

※4 と ※5 から、ed - 1 が「p - 1 の倍数、かつ q - 1 の倍数」であることが必要十分条件となります。言い換えると、

ed = 1 (mod L)

となる L を考えるとき、

L = lcm(p - 1, q - 1)

である場合が、※0 が成り立つ必要十分条件。

L = (p - 1)(q - 1)

が、※0 が成り立つ十分条件となります。(p - 1 と q - 1 の両方とも、2 以外の偶数、 すなわち合成数であることに注意しましょう。)

参考文献