はじめに
C#にはBigIntegerという多倍長整数型が扱えるライブラリがあります。
大学の授業の延長でBigIntegerを使ってRSA暗号のアルゴリズムを書く機会があったのでいろいろ書いてみました。
今回は数学系クラスということで、暗号化や復号や鍵生成等は省きます。
というわけでメモ程度にまとめようと思います。
なお、数学の難しいことはよくわからないのでこの記事では扱いません。
なお、タプル型を使っているので、C#7以上の環境が必要になります。
[github]https://github.com/euglenach/CsharpBigInteger-Math/blob/master/MathB.cs
参考にしたサイト
素数判定いろいろ - フェルマーテスト・ミラーラビン素数判定法
拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜
http://smdn.jp/programming/netfx/mathematics/2_biginteger/
最大公約数
これは、BigIntegerクラスのメソッドにすでに実装されているのを知らずに作ったものです。
RSAアルゴリズムの中でちょくちょく使いました。
public BigInteger GCD(BigInteger x,BigInteger y) {
if(x < y)
SwapNum(ref x,ref y);
return y == 0 ? x : GCD(y,x % y);
}
最大公約数はユークリッドの互除法で求めています。
SwapNumメソッドは2数を入れ替えます。
public void SwapNum(ref BigInteger x,ref BigInteger y) {
BigInteger tmp;
tmp = x;
x = y;
y = tmp;
}
最小公倍数
秘密鍵を生成する計算で使いました
最小公倍数は、最大公約数のアルゴリズムを使えば容易に求めることができます。
public BigInteger LCM(BigInteger x,BigInteger y) {
return x * y / GCD(x,y);
}
偶数判定
これも、BigIntegerクラスのメソッドにすでに実装されているのを知らずに作ったものです。
public bool CheckEven(BigInteger n) {
return n % 2 == 0;
}
一次不定方程式
特殊解
public (BigInteger x, BigInteger y) SpecialLIE(BigInteger a,BigInteger b) {
BigInteger x = 0, y = 0;
_LIE(a,b,ref x,ref y);
return (x, y);
}
private BigInteger _LIE(BigInteger a,BigInteger b,ref BigInteger x,ref BigInteger y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
BigInteger d = _LIE(b,a % b,ref y,ref x);
y -= a / b * x;
return d;
}
SpecialLIEメソッドは、
こちらの記事のアルゴリズムをお借りさせていただき、
とても奇麗なコードだったのでそれにあわせてこのメソッドを作りました。
一般解
public (string x, string y) GeneralLIE(BigInteger a,BigInteger b) {
BigInteger c = GCD(a,b);
var (x, y) = SpecialLIE(a,b);
return ($"x={x}+{b / c}t", $"y={y}-{a / c}t");
}
(x=?+?t),(y=?+?t)という二つの値をstring型で返します。
正直このやり方で良かったのか、と今でも疑念が残ってますが、作ったソフトウェアの仕様上問題なかったので放置してます。
このメソッドはなにかの計算に使うことはなかったので。
一次合同式
public BigInteger Congruence(BigInteger a,BigInteger b,BigInteger m) {
if(m <= 0)
return -1;
for(int i = 0 ; i < m ; i++) {
if((a * i - b) % m == 0) {
return i;
}
}
return -1;
}
一次合同式は、総当たりで1ずつ判定しています。
後述しますが、これだと問題がありますが一旦置いておきます。
素数生成
今回のメインになるところです。
目標としては、100桁の素数を生成することでした。
やり方は、ランダムな100桁の数字を素数かどうか判定し、それを繰り返すことで100桁の素数を取得します。
先ほどの一次合同式の計算方法では、100桁の素数を使うのでさすがにコンピュータがパンクしちゃいます。
なので実際は別の方法で実装しました。とりあえずここでは無視します。
では素数を生成していきます。
まずは乱数を生成します。
BigIntegerの乱数
public BigInteger RandomDigit(int digit) {
Random rand = new Random();
StringBuilder numbers = new StringBuilder();
for(int n = 0 ; n < digit ; n++) {
numbers.Append(rand.Next(0,10).ToString());
}
BigInteger val = BigInteger.Parse(numbers.ToString());
return val;
}
ランダムな数字を100個生成し数値に変換する方法です。
次は、a～bまでの乱数を取得する、みたいなメソッドです。
public BigInteger RandomNext(BigInteger min,BigInteger max) {
if(min == max)
return max;
Random rand = new Random();
BigInteger r = 0;
var digit = rand.Next(GetDigit(min),GetDigit(max) + 1);
while(true) {
r = RandomDigit(digit);
if(min <= r && max >= r)
break;
}
return r;
}
桁数を決める→その桁数の乱数を生成という実装の仕方にしましたがいまいち腑に落ちませんでした。(使えてるしいいや！)
GetDigitメソッドはBigInteger型の桁数を調べます。
public int GetDigit(BigInteger n) {
return (n == 0) ? 1 : ((int)BigInteger.Log10(n) + 1);
}
素数判定
public bool CheckPrime(BigInteger n) {
if(n == 2)
return true;
if(n <= 1 || CheckEven(n))
return false;
var d = (n - 1) >> 1;
while(CheckEven(d))
d >>= 1;
for(int i = 0 ; i < 100 ; i++) {
var a = RandomNext(1,n - 1);
var t = d;
var y = BigInteger.ModPow(a,t,n);
while(t != n - 1 && y != 1 && y != n - 1) {
y = (y * y) % n;
t <<= 1;
}
if(y != n - 1 && CheckEven(t))
return false;
}
return true;
}
素数判定はこちらの記事を参考(ほぼコピペ)にして作りました。
最後に素数生成のメソッドです
public BigInteger GetPrime(short digit) {
BigInteger rand;
while(true) {
rand = RandomDigit(digit);
if(CheckEven(rand))
rand += 1;
if(CheckPrime(rand))
break;
}
return rand;
}
引数に桁数を入れることで素数を生成します。
100桁であれば、1秒もかからず素数を取得できました。
さいごに
なんか変なとこがあれば優しく教えてください。
拙い文章でしたが、少しでも役に立てれば幸いです。
コードをまとめたものはgithubをご覧ください。
閲覧ありがとうございました。