Yuki Nakata's Blog

天才 中ちゃん♪

素数判定法5 繰り返し二乗法の続きになります。

前回はフェルマーテストの変数をlong long型で宣言していました。

long long型でも巨大な数字になると溢れてしまいます。

巨大な素数に対応するためにフェルマーテストをgmpライブラリーを使ってプログラミングしました。

えらい大変やった。脳みそ使うわ。

fermatgmp.c

#include<stdio.h>
#include<gmp.h>

int main()
{
mpz_t m, n, s, a;
mpz_t one, tmp1, tmp2, tmp3;

printf("数字を入力してください\n");
mpz_init(n);
gmp_scanf("%Zd", n);

mpz_init(m);
mpz_sub_ui(m, n, 1); //m = n - 1;

mpz_init(s);
mpz_set_str(s, "1", 10); // s = 1;

mpz_init(a);
mpz_set_str(a, "2", 10); // a = 2;

mpz_init(one);
mpz_set_str(one, "1", 10);

mpz_init(tmp1);
mpz_init(tmp2);
mpz_init(tmp3);

while(mpz_sgn(m)) { //while(m != 0) {
mpz_and(tmp1, m, one); //if (m & 1) {
if (mpz_sgn(tmp1)) {
mpz_mul(tmp2, s, a); //s = (s * a) % n;
mpz_mod(s, tmp2, n);

}
printf("m = ");
mpz_out_str(stdout, 10, m);
printf(" s = ");
mpz_out_str(stdout, 10, s);
printf(" a = ");
mpz_out_str(stdout, 10, a);
printf("\n");

//printf("m = %lld s = %lld a = %lld\n", m, s, a);

mpz_mul(tmp3, a, a); //a = (a * a) % n;
mpz_mod(a, tmp3, n);

mpz_div_2exp(m, m, 1); //m = m>>1;
}

mpz_out_str(stdout, 10, n);
if(!mpz_cmp_ui(s, 1)) {
printf("は素数です\n");
} else {
printf("は素数じゃないよ\n");
}

mpz_clear(m);
mpz_clear(n);
mpz_clear(s);
mpz_clear(a);
mpz_clear(tmp1);
mpz_clear(tmp2);
mpz_clear(tmp3);
return 0;

}

$ gcc fermatgmp.c -o fermatgmp -lgmp
$ ./fermatgmp
数字を入力してください
26588814640432479998443
26588814640432479998443は素数です

私のMac BookProだと一瞬で計算が終わります。
対応するC言語をコメントで残しています。
検証用に計算過程を表示させています。
邪魔であればコメントアウトしてくださぁい。

フェルマーテストの場合、素数を誤判定する可能性があります。

それで改良されたのがミラーラビン法です。

ミラーラビン法を使うことで誤判定の確率が減ります。

ミラーラビン法へ続く予定。いや続かないかも。多分続きます。
 

素数判定法5 フェルマーテストの続きです。

n が素数であるかを調べるために2 ^ nを計算しなければならない、ということでした。

n = 13のとき本来であれば

2 ^ 13 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

2を12回掛けなければいけません。

これを簡単にするのが繰り返し二乗法です。

乗数を分解して、

2 ^ 13 = (2 ^ 1) * (2 ^ 4) * (2 ^ 8)  = 2 * 16 * 256 に分解するのが繰り返し二乗法です。

繰り返し二乗法を使えば計算回数を減らすことができます。

フェルマーの小定理を貼り付けておきます。

2 ^ (n - 1) mod n = 1 

c言語プログラム 
#include<stdio.h>

int main()
{
long long m, n;
long long s = 1;
long long a = 2;
printf("数字を入力してください\n");
scanf("%lld", &n);
m = n -1;
while(m != 0) {
if (m & 1) {
s = (s * a) %n;
}
printf("m = %lld s = %lld a = %lld\n", m, s, a);
a = (a * a) % n;
m = m>>1;
}
if (s == 1) {
printf("%lldは素数です\n", n);
} else {
printf("%lldは素数ではありません\n", n);
}
}

$ gcc fermat.c -o fermat

$ ./fermat

数字を入力してください

9999637

9999637は素数です 

素数判定法6 フェルマーテスト GMPライブラリ に続きます。

参考サイト
繰り返し二乗法

lenovo yoga
lenovoのyoga というノートパソコンを持っています。

ディスプレイが360度回転するノートPCです。

コスパが良いんで気に入ってます。


ところがPCを起動するとディスプレイが真っ黒になってしまいました。

起動するとlenovoの文字が数秒表示された後、何も表示されません。

一瞬故障したのかと思いましたが、違うようです。

lenovoのロゴが数秒表示されるのでディスプレイも問題なし。

実はこれ、ディスプレイの映像が外部出力になってしまったときの現象です。

ディスプレイの映像を外部モニターに送ることができるんです。

その機能が有効になってしまっています。


解決方法

セカンドスクリーンのF10キー このマークを押す

そのままF10キーを押してください。反応ないときは何回かF10キーを押してください。

映像がディスプレイに表示されるようになったと思います。


 

前にも書きましたが、映画の借王が大好きでした。

15年前はレンタルビデオでしたが、今はyoutubeです。

1作100円で見ています。便利になりましたね。

借王シリーズ4まで見ました。
借王4


安西はんと青柳様。

青柳様 「安西はん、10億のうち1億今月中に返しておくれやす。」

安西はん 「今月中ですか、融資という形でよろしいでしょうか?」

青柳様 「10億預けているのに、どうして借金せなあかんの?、うち借金嫌いどすねん。」

安西はん 「。。。かしこまりました。では今月中に1億。」 

という図。

このやりとりだけでも見る価値があります。w

 

ホームページやブログのフォント選びについてです。

最近、遊ゴシック体というフォントを使っているサイトをよく見かけます

遊ゴシック体とはwindows8.1、mac osx10.9以降では標準搭載されているフォントです。

自分のホームページやブログを持っている人は遊ゴシック体を基本フォントとして
指定してみましょう。

もちろん、このnakatayuki.comでは遊ゴシック体を利用しています。

このcssでは以下のようにフォントを指定しています。

font-family: '游ゴシック体', 'Yu Gothic', YuGothic, 'ヒラギノ角ゴシック Pro', 'Hiragino Kaku Gothic Pro', メイリオ, Meiryo, Osaka, 'MS Pゴシック', 'MS PGothic', sans-serif;

フォントだけなのですぐにできます。

ライブドアブログの場合にはブログ設定 -> デザインPC -> カスタマイズからフォントを変更することができます。

body の箇所でフォントの指定があると思います。

ぜひやってみましょう。


hex-a-hop
hex a hopはlinuxのパズルゲームです。

すぐに始めることができます。

 $ sudo apt-get install hex-a-hop

でインストールできます。

$ hex-a-hop

でゲームが起動します。

緑色のマス目を全て破壊するとクリアです。

緑色のマス目は一度乗ると壊れるようになっています。

頭を使うゲームで面白いです。

メニューや、ヒントもすべて日本語で表示されますので、すぐに楽しめると思います。

できるところまで進んでみます。
 

借王
不敵な笑みを浮かべる哀川翔

昔、借王(シャッキング)という映画が大好きでした。

借金で首が回らなくなった3人組が詐欺をする、という映画です。

個性を発揮して詐欺ミッションを遂行する、という意味でミッションインポッシブルに近い感覚がして面白いのです。

借王で検索しているとyoutubeでヒットします。

youtubeで映画が見られるようになっているんですね。知りませんでした。

しかも1作品たったの100円です。

72時間でしたら100円で映画を観ることができます。

もちろん映画の作品によって価格は変わると思いますが、昔の映画でしたら100円程度で見られるのではないでしょうか。

昔好きだった映画が誰にでもあると思います。ユーチューブで見ましょう。懐かしいですよ。

シャッキング2
支払い方法は簡単で、クレジットカードかpaypalで支払うだけです。

youtubeで映画が見られるというのは素晴らしい。 

最新の映画も見られるようにすればいいのに。

映画館にお金を払う人はyoutubeにもお金を払うでしょう。

1作品500円程度なら喜んで払うと思いますけど。


そんなわけで15年ぶりぐらいに借王を観ました。いやー、面白い。

人間の感覚はそんなに変わらないですね。

哀川翔が若い。かわいい。冒頭の哀川翔の顔を見てください。いい表情してるわ。

志賀勝がいい味出してる。

このまま全シリーズ見てしまいそうです。
 

↑このページのトップヘ