RSA暗号の解説に出てくる数値の逆数のmod

RSA暗号に紹介には、必ず次のような式がでてきます。

これ

今日は、この式について解説します。
といっても・・・すみません。言い訳になりますが、
数学科出身ではなく、間違ったこというかもしれません。
それをふまえていただいて・・・解説させていただきます。

まず、m = (p – 1)(q – 1) とすると、式は次のようになります。

さて、この式、意味が分かりますでしょうか。
ここで、mod mというのは、mで割った余りとなります。
つまり、式通りの意味を考えると x^-1 =(1/x) を計算して、
m で割った余りが y となります。

しかし、よく考えてください。
言い忘れていましたが、x, y, m とも整数なのです。
x が整数の時点で、 x^-1 =(1/x) という式を計算すると、
小数点付きの数値となり、小数点付きの数値に対して、
整数 m で割る？というよく分からないことが起きます。

じつは、これは逆数とはいってもモジュラ逆数と呼ばれるものなのです。
つまり、(1/x)みたいなことをしてはいけないのです。たぶん？

さて、モジュラ逆数となると、
上記のこれまでの式は一体どういう意味なのか。
実は、次のような意味になります。

x と y を掛け算して、m で割った後の余りが 1 となります。

つまり、これまでの式は、
上記の計算結果を満たすような y を求める式なのです。

例題と行きましょう。
x = 3, m = 10 としたときの y は一体いくつでしょうか。

これの y を求めてみましょう。

・・・

求める過程は、モジュラ逆数の紹介にある
拡張ユークリッド互除法で最大公約数など、
いくつか値を求める必要がありまして、
ここでは省略します。

そして、答えを求めると y = 7 が導かれます。

実際に計算してみると・・・

余りが 1 となり、ぴったりとなります。

なお、Java などでは、
この y の値を BigInteger の modInverse メソッドで計算することが可能です。

	public static void main(String[] args) {
		System.out.println(new BigInteger("3").modInverse(new BigInteger("10")));
	}

Javaで高速に平方根の逆数を求めるシェーディング言語について調べてたら平方根の逆数を高速に求めるrsqrt関数というのがあるらしいことが分かった。それで、この rsqrt について調べてたら、Fast inverse square rootっていう高速に計算できる記事を見つけた。日本語だと、井尻さんのサイトの高速根号計算 (fast sqrt […] Posted in アルゴリズム
ランダムな添え字こんな感じで。 Java /** * 指定した長さの一様分布な重複しないランダムな添え字を作成します。 * @param length * @param seed * @return */ public static int[] getRandomIndex(int length, long seed) […] Posted in アルゴリズム
麻雀の待ち判定問題 part1 昨晩は、話題の「あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定」をやってました。意外に時間がかかって大変でした。こんな時期にやるんじゃなかった。眠たい。(p_-) 正直3時間ちょっとかかってしまいました。テンパイ（1113335558888）とチートイツ判定なしです。以下は、作った後の感想です。 3時間が短いと感じまし […] Posted in アルゴリズム
麻雀の待ち判定問題 part2 「あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定」 [西尾泰三，ITmedia] 2010年04月03日 00時00分 […] Posted in アルゴリズム
指定した範囲の乱数を作成したい（後編）みなさん、こんにちは。今日は、昨日の続き、「指定した範囲の乱数を作りたい」を続きに話していきたいと思います。というか、解答編みたいな感じです。指定した範囲の乱数を作成したい（前編）指定した範囲の乱数を作成したい（後編）←いまここっ！指定した範囲の乱数を作成したい（実戦編）・それでは、ちょっとおさらいをしながら進めていきます。今回は、 […] Posted in アルゴリズム
Bresenhamアルゴリズムで線分の計算は早いのかな以前、直線を描くのにこんなのを作った。特に工夫点もない、素直な方法である。 #module "linem" #deffunc line2 int line_x1,int line_y1,int line_x2,int line_y2 line_xabs = abs(line_x1-line_x2) line_yabs = […] Posted in アルゴリズム
何をしているソースコードでしょうかさて、何しようとしてるでしょうか。 public class Test { public static void main(String[] args) { int width = 4,height = 8,size = width * height; int[] memo = new int[size]; int[][] masu = […] Posted in プログラミング
指定した範囲の乱数を作成したい（前編）みなさん。指定した範囲の乱数を作りたい場合は、どうしているでしょうか。今日は、指定した範囲の乱数生成の小ネタを紹介します。指定した範囲の乱数を作成したい（前編）←いまここっ！指定した範囲の乱数を作成したい（後編）指定した範囲の乱数を作成したい（実戦編）・さて、例えばサイコロを作りたいと思います。サイコロの目は1～6ですね。そして乱数生成器が用意されてい […] Posted in アルゴリズム
HSPでsleep sortを実装してみたこの前、sleep sort(元ネタ)というのを知って、 HSPでSetTimerでそれっぽいのを作ったのですが、掲示板のwait0000さんが作ったのと普通に被ってしまったので寝かせてました。うん。でも5月に1度も投稿してなかったので、投稿します(^^) 実用性とかそういうのなしで、発想力がすごい。 //sleep […] Posted in アルゴリズム
指定した範囲の乱数を作成したい（実戦編）みなさん、こんにちは。さて、前回、前々回にわたって、指定した範囲の乱数の作成の仕方を書きました。改めて奥が深いですね。読み忘れた方のためにリンクしますっ(^o^) 指定した範囲の乱数を作成したい（前編）指定した範囲の乱数を作成したい（後編）指定した範囲の乱数を作成したい（実戦編）←いまここっ！これまでの話では、小さなより精度が […] Posted in アルゴリズム