Miller-Rabin 100桁の素数生成

[clear]

ミラーラビンアルゴリズムを用いてランダムに100桁の素数を生成するプログラムを実装したいのですがプログラミング自体が全くと言っていいほど得意でないので全く歯が立たず困っています。

Miller-Rabin testの繰り返し回数は5回でお願いします。

基本的には示されたアルゴリズムをコード化すればいいのはわかります。
100桁なので配列が複数必要になると思うのですがどうやればいいかわかりません。

丸投げになってしまって申し訳ないのですが、提出が12日(月)正午で、ここ3日間考えて分からなかったので質問させていただきました。


algorithm miller-rabin-test(n,l)
begin
　Compute odd number u and positive integer k such that n = u*2^k;
　for i ← 1 to l do
　　if M-R-T(n, u, k) = NO then return(NO);
　return(YES);
end

function M-R-T(n, u, k)
begin
　Pick a ∈ {2, 3, ..., n-2} at random;
　b ← a^u mod n;
　if b ∈ {1, n-1} then return(YES);
　for i ← to k-1 do begin
　　b ← b^2 mod n;
　　if b = n-1 then return(YES);
　　if b = 1 then return(YES);
　end;
　return(NO);
end

[みけCAT]

まずは使用するプログラミング言語を決めてください。

100桁の素数

何進数でですか？

[みけCAT]

素数かどうかは無視して、とりあえず「100桁」の数を生成するプログラムは実装できますか？

[clear]

まずは使用するプログラミング言語を決めてください。

100桁の素数

何進数でですか？

説明が足りず申し訳ありません。
言語はC言語で、指定はないので10進数お願いします。

素数でなくとも、100桁の整数を生成するプログラムをすぐには書くのは難しいです。

[みけCAT]

The GNU MP Bignum Libraryなど、非標準のライブラリの使用は許されますか？

[clear]

The GNU MP Bignum Libraryなど、非標準のライブラリの使用は許されますか？

多倍長計算を高速にするライブラリのようですがそういった非標準のライブラリはなしでお願いします。

[みけCAT]

提出ということは、講義の課題かなんかですか？
講義であれば、これ以前の回でC言語による多倍長演算は習いましたか？

[みけCAT]

そもそも、何を提出するべきなのですか？
課題の内容によっては、諦めて「ミラーラビンアルゴリズムを用いてランダムに100桁の素数を生成するプログラム」ではなくもう少し簡単なプログラムを書いた方が得策かもしれません。

[clear]

ミラーラビンアルゴリズムを用いてランダムに100桁の素数を生成するプログラム

提出するのは
ミラーラビンアルゴリズムを用いてランダムに100桁の素数を生成するプログラム
です。(.cファイル)

C言語の講義ではなく離散アルゴリズムの講義なので多倍長演算については習っていません。

[白い変人]

>基本的には示されたアルゴリズムをコード化すればいいのはわかります。

本当に分かっているのかが個人的には疑問です。
少なくとも、質問者様ご自身が提示されたアルゴリズムが、私には素数を生成するアルゴリズムには見えません。

質問者様は丸投げとご自身で認めていらっしゃるようですが、

>「3日間考えて分からなかったので」
>「提出が12日(月)正午で」

という部分も正直引っかかっていまして。

と言いますのも、ミラーラビンアルゴリズムを用いて100桁の素数を扱える様にするには、C言語上で100桁以上の数値を扱えるようにする必要があると考えられますよね? (unsigned long long 型でも 0 ～ 18,446,744,073,709,551,615までしか扱えない。)

つまり、100桁以上の計算を出来るようにする処理から作成しなければならない訳です。

とりあえず動けば良いだけの即席のプログラムであればこの限りでは無いのかもしれませんが、ちゃんとした実用的な動作が見込める様に、C言語上で100桁以上の数値の演算を行えるようにするだけでも、コードの組み方次第では1000行以上のコードになりかねません。

それを用意すれば、その後の「100桁の疑似乱数生成」「その疑似乱数の素数判定」(←恐らくそういう事をやりたいのだろうと汲み取った。)も割とコード化し易くなるとは思いますが、C言語のプログラミングスキルがある人でも、上記全てを1からCでコーディングすると5～6日では少々ハードと言えるでしょう。

私の場合、既に技術が蓄積されていますので、12日までに代わりに作ってくれと言われたら過去の遺産のコピペを使えば作れるとは思います。(それでも、多分、私はやらないけど。)

でも、それを12日までに全部1から作ってくれと言われたら、仮にプログラミングスキルがある人でも御免被りたいとなるかもしれません。(工数が多くなりかねないから。)

何が言いたいのかと言いますと、上記プログラムを完成させるには十分だろう潤沢な時間が与えられていたにも関わらず、質問者様はそれをしなかった可能性を疑っています。

悪い意味で捉えないので欲しいのですが、仮に私の指摘(十分な時間が与えられていたにも関わらず課題を放置した事)が図星だった場合、質問者様はただ単にやる気が無いだけの可能性もあると思います。

「興味が無い事」や「やる気が無い事」に力を注ぎ込んでも成就しない可能性がありますので、仮にやらなくても済む課題であるならば諦める事や、人生の進路の変更等を視野に入れる事も質問者様の人生の為なのではないかと、現時点ではアドバイスしたいと思います。

C言語の知識が乏しい人が普通にやったら5～6日程度で解決出来るだろう課題には見えません。

[かずま]

algorithm miller-rabin-test(n,l)
begin
　Compute odd number u and positive integer k such that n = u*2^k;
　for i ← 1 to l do
　　if M-R-T(n, u, k) = NO then return(NO);
　return(YES);
end

function M-R-T(n, u, k)
begin
　Pick a ∈ {2, 3, ..., n-2} at random;
　b ← a^u mod n;
　if b ∈ {1, n-1} then return(YES);
　for i ← to k-1 do begin
　　b ← b^2 mod n;
　　if b = n-1 then return(YES);
　　if b = 1 then return(YES);
　end;
　return(NO);
end

n = u*2^k だったら、n は 2の倍数なので素数ではありません。
Wikipedia を見たら、n-1 = u*2^k でした。

　if b ∈ {1, n-1} then return(YES);
と
　if b = n-1 then return(YES);
　if b = 1 then return(YES);
とは、同じ意味ですよね。C で書くと、
　if (b == 1 || b == n-1) return YES;

多倍長計算を実装するのは面倒なので unsigned long long で、
9桁までなら、アルゴリズムの検証ができるかやってみました。

コード:

#include <stdio.h>   // printf
#include <stdlib.h>  // srand, rand
#include <time.h>    // time

#define YES  1
#define NO   0

typedef unsigned long long TYPE;

TYPE mod_pow(TYPE x, TYPE y, TYPE n)
{
    TYPE z = x;
    while (--y > 0) z = z * x % n;
    return z;
}

TYPE MRT(TYPE n, TYPE u, TYPE k)
{
    if (n <= 3) return YES;
    TYPE a = rand() % (n - 3) + 2;
    TYPE b = mod_pow(a, u, n);
    //printf("n=%llu, u=%llu, k=%llu, a=%llu, b=%llu\n", n, u, k, a, b);
    if (b == 1 || b == n-1) return YES;
    for (TYPE i = 0; i < k; i++) {
        b = mod_pow(b, 2, n);
        if (b == 1 || b == n-1) return YES;
    }
    return NO;
}

TYPE miller_rabin_test(TYPE n, TYPE l)
{
    TYPE u = n - 1, k = 0;
    while ((u & 1) == 0) u >>= 1, k++;
    for (TYPE i = 0; i < l; i++)
        if (MRT(n, u, k) == NO) return NO;
    return YES;
}

int main(void)
{
    srand(time(0));

    printf("start n: ");
    TYPE n;
    if (scanf("%llu", &n) != 1) return 1;
    n |= 1; // 奇数にする

    printf("times k: ");
    int k;
    if (scanf("%d", &k) != 1) return 1;
    k /= 2; // 奇数だけなので回数は半分

    for (int i = 0; i < k; i++, n += 2)
        if (miller_rabin_test(n, 5) == YES) {
            printf(" %llu", n);
            fflush(stdout);
        }
    printf("\n");
    return 0;
}

実行結果

コード:

start n: 99999900
times k: 100
 99999931 99999941 99999959 99999971 99999989

すごく時間がかかるので、多倍長計算でも 100桁やるのは大変だと思います。