プログラミング Tips

ITエンジニアの雑記ブログ。
IT関連ニュースの考察や、プログラミングに関するTipsの備忘録として…
育児や日常の雑記帳としても、記事を投稿していきます。

プログラミングと日常生活に関する情報を発信しています。

カテゴリ: 開発

RSA暗号(秘密鍵と公開鍵)の仕組みを勉強してみた!

暗号化と複合化で異なる鍵を使う「公開鍵暗号方式」は、SSL通信などで用いられる重要かつ有名な技術である。

この公開鍵暗号方式で有名なものに「RSA暗号」があり、これは内緒で選んだ2つの素数から公開鍵と秘密鍵を作り、2つの素数の積を公開する。従って、もしも2つの素数の積を素因数分解できれば、暗号を解読が可能。

ただし大きな素数の積の場合、最新のコンピューターを用いても素因数分解は実用的な時間では終わらない。
素因数分解を効率的に行うアルゴリズムがまだ見つかっていないためである。


素因数分解の関数を作る

引数に指定された整数nを素因数分解し、その結果を表示するprimeFactorization関数を作成する。

この関数は、引数にnに100を指定すると、

100 = 2 * 2 * 5 * 5

と表示する。素因数分解のアルゴリズムには、高度な数学を使った技法も考案されているが、ここは単純な技法に工夫を加える手法とする。

下記の例は、まだ工夫を加える前のprimeFactorization関数とテスト用main関数。

main関数では、キーボードから1以上の整数入力を受け、それを引数nとしてprimeFactorization関数を呼び出す。

#include <stdio.h>

void primeFactorization(unsigned int n) {
    unsigned int, a, counter;

    printf("%u = ", n);
    counter = 0;
    a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            printf("%u * ", a);
            n /= a;
        }
        else
        {
            a++;
        }
        counter++;
    }
    printf("%u\n", n);
    printf("counter = %u\n", counter);
}

int main(int argc, char* argv[]) {
    unsigned int n;

    printf("1以上の整数を入力してください:")
    scanf("%u", &n);
    primeFactorization(n);
    return 0;
}

primeFactorization関数では、aで繰り返しnを割って(割切れることを確認後)、nの値を更新。aの初期値は、最小の素数2である。nが、aで割切れる可能性があるのは、n ≧ aの2乗の時だけであるため、それをwhile分の繰り返し条件にする。

例えば、100を素因数分解する時、nの値が100, 50, 25, 5と更新された時点で、n ≧ 2の2乗という条件がfalseになり、繰り返しが終了となる。

while文を抜けてから、最後に残った5を付け足して表示する。

後で加える"工夫"の効果を確認できるように、while文の繰り返し回数をcounterという変数でカウントし、100および429467295(unsigned int型の最大値)を素因数分解結果は以下になる。

| 1以上の整数を入力してください:100
| 100 = 2 * 2 * 5 * 5
| counter = 6

| 1以上の整数を入力してください:429467295
| 429467295 = 3 * 5 * 17 * 257 * 65537
| counter = 259

繰り返し回数が減るように工夫する

100の素因数分解であれば実行時間は一瞬で、実行上問題ない。

しかし、数字が大きくなるほど時間がかかる。よって、primeFactorization関数の処理を工夫してみる。

気づいている方はいるかもしれないが、ポイントはwhile文の中で、aの値が2, 3, 4...と1ずつ増えていく部分である。例えば、100の場合、2と5で割切れるかを2回ずつチェックしただけでなく、3, 4でも割切れる事の確認をした。

素数である3はチェックする必要があるが、素数でない4をチェックすることは無駄になる。

するとaが素数であるか?否か?の確認を実施した上で、素数であることを確認してから割り算を実施すべきである。しかし、これでは「aの素数確認」に時間がかかってしまうことになる。

よって、ここでは処理に時間のかからない簡易的な素数確認方法を採ることとする。

具体的には、5以降の数では、2の倍数、3の倍数は素数でないとして繰り返しかた除外する。

aのインクリメント法を工夫して回数を減らせる。
5以上の整数を並べてみると、

| 5, 6, 7, 8, 9, 10...

となる。この並びは、「奇数⑸、偶数かつ3の倍数⑹、奇数⑺、偶数⑻、奇数かつ3の倍数⑼、偶数⑽」であり、11以降も同じパターンで繰り返される。よって、2の倍数と3の倍数をスキップするには5以降の1の増加分を+2, +4, +2, +4…とすればよい。

以下に改良したprimeFactorization関数を載せる。

まず、aを2および3の倍数でない数で割る。次にaの初期値を5として、2および3の倍数でない数で割る。
次にaに2と4を交互に加える

a += (inc ^ 6);

少し変わった書き方なので、解説すると以下の通りである。
"inc"は増分、"^"は排他的論理和(XOR)演算。2と4を2進数で表すと、"0010", "0100"になる。これらを交互に切り替えるには、"0110"つまり"6"とXOR演算を行えばよい。XOR演算は、1に対する桁を反転し、0に対する桁を変化させない。つまり、

0010 XOR 0110 = 0100
0100 XOR 0110 = 0010
0010 XOR 0110 = 0100

となり、1, 4の繰り返しを切り替えられる。

この方法を用いて、先ほどの4294967295を実行すると、繰り返し回数が259→130回に減っていることがわかる。
つまり120回は無駄な繰り返しだったことがわかる。

乱数を生成するアルゴリズムを勉強してみた!!

アプリやゲームをプログラミングする時、しばしば乱数を使用する。
ほとんどのプログラミング言語で、乱数を生成する標準ライブラリが準備されているが、内部的にどのように生成しているのかを考えたことはなかった…

そこで乱数を生成するアルゴリズムを勉強してみようと思った。


擬似乱数

PC, プログラム自らは情報を生み出すことはできず、何らかの計算式を使って、見かけ上ランダムな数値を生成する。このような乱数を「擬似乱数」と呼ぶ。

例えば、C言語の標準ライブラリには0〜32767の範囲で乱数を生成するrand関数がある。
乱数生成前のウォーミングアップとして、rand関数を使用してみる。以降では、擬似乱数を単純に「乱数」と表現する。

rand関数を使用する前に準備すべきことがある。それは乱数を生成する式の中で使われる最初の値を変えることである。この値を「乱数の種」と呼ぶ。

乱数の種

「乱数の種」を変えないと、rand関数は毎回同じパターンの数列を返す。
C言語は、srand関数を使って乱数の種を設定できる。srand関数の引数に、乱数の種を与える。

乱数の種には、time関数の戻り値を使うのが定番テクニック。

time関数は、1970年1月1日0:00からの経過時間を返す。この値は、プログラムを起動するたびに異なるため、毎回値を変えるべき乱数の種として好都合。

srand関数とrand関数の使い方を示すプログラムを示す。実行すると10個の乱数を表示する。

どのような乱数になるか?はプログラムを実行したタイミング(時間)次第。

ちなみに、8行目を"/* */"で囲んでコメントアウトしてみると、面白い結果が得られる。
何度プログラムを実行しても、毎回同じ結果が表示される。

#include <stdio.h>
#include <stdlib.h> //srand関数とrand関数のため
#include <time.h>   //time関数のため

int main(int argc, char* argc[]) {
    int i;
    //乱数の種を設定する
    srand((unsigned int)time(NULL));

    //乱数を10個生成、表示する
    for (i = o; i < 10; i++) {
        printf("%d\n", rand());
    }
    return 0;
}

乱数生成アルゴリズム⑴ ー線形合同法

C言語のrand関数内部で使用されていることで有名な「線形合同法」。
以下の斬化式(数列の1つ前の値で、その次の値を求める式)で乱数を生成する方法。

この式は、n番目の乱数Xnを、その1つ前の乱数X(n-1)を使った計算で得ることを示している。

modは割り算のあまりを求める演算子(C言語では%演算子)。

Xn = (A x Xn-1 + B) mod M

この式において、A, B, Mは、0より大きな整数の定数。
X0が「乱数の種」に相当する。

X0を式の右辺において得られる計算結果が、最初の乱数X1になる。
以下同様に、X1を右辺においてX2を得る。X2を右辺においてX3を得る…と繰り返し計算する。

#include <stdio.h>

//1つ前の乱数
int random;

//乱数の種を設定する関数
void srand2(unsigned int seed) {
    random = seed;
}

//乱数を生成する関数
int rand2() {
    random = (2 * random + 3) % 7;
    return random;
}

int main(int argc, char* argv[] {
    int i;
    //乱数の種を設定する
    srand2(3);
    //乱数を10個生成する
    for (int i = 0; i < 10; i++) {
        printf("%d\n", rand2());
    }
    return 0;
}

上記において、A = 2, B = 3, M = 7 として生成した乱数生成rand2関数と、乱数の種を設定するsランD2関数。
C言語の標準ライブラリの関数と間違えないように、関数名の末尾に2を付けた。

グローバル件数randomに格納するだけ。rand2関数は、線形合同法の式に従って乱数を計算し、その値をグローバル変数randomに格納し、戻り値として返す。

テスト用のmain関数では、srand2関数の引数に、time関数の戻り値ではなく3(適当に選定)を与えている。

擬似乱数には周期性がある

rand2関数の

random = (2 * random + 3) % 7;

の部分を見れば、乱数生成の仕組みがわかる。
直前に生成された値を2倍して3を加えることによってできる数列が、乱数のようにみえる。

ただし7で割った余りのため、生成される乱数の範囲は、0~6に制限される。
この結果、同じ数列が繰り返されることがわかる。

擬似乱数の特徴であり、「周期性」と呼ばれている。

多くの選択肢から最適解を見つける方法を勉強してみた!!

最適化問題とも言われ、たくさんある選択肢の中から、最適な解を選び出す手法で、「グリーディ法」と呼ばれている。

グリーディ法は近似アルゴリズムの一種で、最適解ではなくてもそれほど悪くない解を(近似解)を得る手順のことで、"BEST"より"BETTER"を探し出す手法と言うとわかりやすいと思う。

最適解を得るのに、膨大な計算を要する場合、短時間で解を得るために、近似アルゴリズムが用いられることがある。

実際において、近似解であっても無駄がなければ(誤差が一定以内)十分と判断できるはずであり、短時間で効率的に「解を得る」場合に用いられることになる。


まずは【硬貨の交換問題】から!

問題

あるお店で、、税込213円の商品を購入した場合、お客さんは1000円札を出しました。
お釣りは、

1000 - 213 = 787

です。
できるだけ少ない枚数でお釣りを返すには、どのような組み合わせにすべきでしょうか?

解答例

この問題の答えは、

  • 500円 x 1
  • 100円 x 2
  • 50円 x 1
  • 10円 x 3
  • 5円 x 1
  • 1円 x 2

となる。この解を得るためには、「できるだけ大きな硬貨を使う」と考えたと思う。

つまりこれが『グリーディ法』である。

グリーディ(Greedy)とは、「貪欲な」という意味で、「可能な限り大きな硬貨を使う」というアイデアを『貪欲』と表現しているのである。

プログラム例

ではこれを実際のプログラムにするとどのようになるのか?
例を以下に記してみる。

#include <stdio.h>

int main(int atgc, char* argv[]) {
    //お釣り、枚数、枚数の合計、ループカウンタ
    int change, n, sum, i;

    //硬貨の種類
    int val[] = {500, 100, 50, 10, 5, 1};

    printf("お釣りは?");
    scanf("%d", &change);

    sum = 0;
    for (i = 0; i < 6; i++) {
        n = change / val[i];
        printf("%d円硬貨 : %d枚", val[i], n);
        sum += n;
        change %= val[i];
    }

    printf("硬貨の合計枚数: %d枚\n", sum);

    return 0;
}

このように、"%"の計算を用いて、除算の余りを得る演算を繰り返すことで、より小さい硬貨へ交換するための残金を求めることができる。

現在の日本の硬貨であれば、「できるだけ大きな硬貨を使う」というグリーディ方で、最適解が得られる。

もしも新たにな硬貨が追加されたらどうなる?

グリーディ法では最適解が得られない場合が生ずる。

例えば、400円硬貨が追加された場合どうだろう?

先ほどのプログラム例で、

int val[] = {500, 400, 100, 50, 10, 5, 1};

for (i = 0; i < 6; i++)

の部分を

for (i = 0; i < 7; i++)

に健康して、お釣り800円を置き換える硬貨の枚数を求めてみる。

400円硬貨があるなら、

  • 400円 x 2

が、最適解となるが、プログラム実行の結果は、

  • 500円 x 1
  • 400円 x 0
  • 100円 x 3
  • 50円 x 0
  • 10円 x 0
  • 5円 x 0
  • 1円 x 0

となる。「できるだけ大きな硬貨を扱う」というグリーディ法では、最適解を得られないことがあるというのが特徴。
ただし、

  • 1円 x 800

といったおかしな解にもなりません。

これと比較した時、今回の例では、硬貨の枚数が2枚でも4枚でも大きな差はないと言え、「4枚という近似解は十分に実用的」と言える。

以上から、

「プログラミングをする以上、正確無比な最適解を常に求めなければならない!!」と思いがちではあるが、実生活において、「最適解を求めるまでに、時間を要するのであれば、近似解を1秒で求めた方が実用的だ!」と判断する場面は多い。

このことからプログラムにおいても、『実用性』を考慮した設計・仕様が重要と言える。

効率よくデータを並べ換える方法を勉強してみた!

プログラムを開発していて、配列はよく使うが、効率よく並べ換えるアルゴリズムに「クイックソート」がある。
アルゴリズムは知っているが、プログラムにおこすとなると少し難易度が上がる。

「クイックソート」アルゴリズムとは?

クイックソートは、配列を整列するアルゴリズムの一種。
概要は、
配列の適当な要素を基準値にして、より小さい要素が前、より大きい要素が後ろになるように移動する。
基準値の前側の部分配列と、後ろ側の部分配列で、同じ処理を繰り返し行う。
である。

プログラムに落とし込むのは少し困難

クイックソートのプログラムを書くポイントは、基準値との大小関係において、配列を2つの部分配列に分けることにあるが、
これだけでプログラムに表現していくことは困難。よって、ここではこの書き方を習得していく。

書き方には複数のバリエーションがあるが、ここでは簡単な方法を書く。

そのために…

  • 適当な要素とは何番目の要素なのか?
  • 前側や後ろ側に移動するにはどうしたらよいか?
  • 基準値と同じ値の要素の処理はどうすればいいか?

という疑問が残る

これらの疑問を解決しよう!

適当な要素とは?

配列の先頭の要素を基準値にすればいい!!
残りの"要素を先頭+1"(先頭の次)、および末尾から1つずつチェックして、大小関係に応じて両者を入れ替えれば、要素の移動ができる。
この際に「より小さい」「より大きい」ではなく。「以下」「以上」で比較すれば、基準値と同じ値の要素も処理できる。

変数leftは、配列の要素を先頭+1からたどるループカウンタ。変数rightは、配列の要素を末尾からたどるループカウンタ。

ループの終了条件は、"left>= right"となる。
"left > right"ならチェックが終わっているが、最終的にleftとrightが同じ要素を示す場合もあり得るため、left>=rightという終了条件になる。

処理の最後に、rightが示す要素と基準値を入れ替えることにも注意。

ループ終了時のrightは、基準値以下の要素を指す。基準値は、rightが指す要素より大きい場合があるので入れ替える。

この手順を"arrangerArray"関数にまとめると以下のようになる。

あとでクイックソートを行う際に、繰り返し適応するので、部分配列の先頭の要素を引数"head"、末尾の要素を引数"tail"で指定する。

int arrangerArray(int a[], int head, int tail) {
    int pivot, left, right, temp;

    pivot = a[head];    //基準値
    left = head + 1;    //先頭+1からたどるループカウンタ
    right = tail;       //末尾からたどるループカウンタ

    //大小関係に応じて要素を入れ替える
    while(-1) {
        //配列を先頭+1からたどる
        while (left < tail && pivot > a[left]) left++;

        //配列の末尾からたどる
        while (pivot < a[right]) right--;

        //ループの終了
        if (left >= right) break;

        //leftとrightが刺す要素を入れ替える
        temp = a[left];
        a[left] = a[right];
        a[right] = temp;

        //次の要素チェックに進む
        left++;
        right--;
    }

    //最後に基準値とrightが指す要素を入れ替える
    a[head] = a[right];
    a[right] = pivot;

    //部分配列を区切る要素の番号を返す
    return right;
}

クイックソートを行う関数を作成してみる

部分配列に繰り返しarrangeArray関数を適応する処理は、再帰呼び出しを使って書くと容易。

quickSort関数の引数startとendには、ソートを行う配列の先頭と末尾の要素番号を指定する。
最初にquickSort関数を呼び出すときには、これらの引数に配列全体の先頭と末尾の要素番号を指定する。
quickSort関数が再帰呼び出しされる時、これら引数に部分配列の先頭と末尾の要素b何号が指定される。

void quickSort(int a[], int start, int end) {
    int p;  //部分配列を区切る要素番号

    //要素が2つ以上ある配列なら処理を行う
    if (start < end) {
        //基準値と大小関係に応じて2つの部分配列に分ける
        p = arrengeArray(a, start, end);

        //前側の部分配列に同じ処理を適応する
        quickSort(a, start, p - 1)

        //後側の部分配列に同じ処理を適応する
        quickSort(a, p + 1, end);
    }
}

あらかじめ"arrangeArray"関数を作っておいたので、quickSort関数を作成したため、
"quickSort"関数の処理をスッキリ書けた。

"arrangerArray"関数で行なっている処理が、クイックソートのポイント。

↑このページのトップヘ