暗号総崩れ-素数判定が多項式時間で可能

【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明
http://news2.2ch.net/test/read.cgi/newsplus/1028876818/

世の中どうなってしまうのでしょう?

出たなインド人

　γ~三ヽ
　(三彡０ﾐ)
　（　´∀｀）
　（_つノﾉｌ|つ
　 Lｌ_|_|_ｌ.||
　（_＿）＿）

へー、すごいんだね。。。。

コリア困った

俺のセキュリティ対策は無駄だったのか･･･

賞金1.00万円の暗号解読コンテストを開いてた厨房、大慌て。

そっすか！ｱｲｺﾞｰ！

タコ式自慰で化膿？

http://science.2ch.net/test/read.cgi/math/1028813059/

つか、誰か馬鹿にもわかるように説明してよ。

　　 　 ∧＿∧∩　／￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　 （　´∀｀）/＜　先生！ 1行目の
　＿ / /　　 /　　　＼　if ( n is of the form ab, b > 1 )
＼⊂ノ￣￣￣￣＼　 ＼　からしてもうわかりません！
　||＼　　　　　　　　＼ 　 ＼＿＿＿＿＿＿＿＿＿＿＿＿
　||＼||￣￣￣￣￣||
　||　 ||￣￣￣￣￣||
　 　 .||　 　 　 　 　 ||

　　 　 ∧＿∧∩　／￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　 （　´∀｀）/＜　先生！ 2行目の
　＿ / /　　 /　　　＼　r = 2;
＼⊂ノ￣￣￣￣＼　 ＼　は理解しました！
　||＼　　　　　　　　＼ 　 ＼＿＿＿＿＿＿＿＿＿＿＿＿
　||＼||￣￣￣￣￣||
　||　 ||￣￣￣￣￣||
　 　 .||　 　 　 　 　 ||

ところで、
素数判定が多項式時間＝暗号総崩れ
は結びつくのか？

カンプールのインド工科大学のManindra Agrawal、Neeraj KayalおよびNitin Saxenaが、
素数判定を多項式時間(polynomial time)で可能なアルゴリズムを発見、証明した。

素数判定(が困難であること)は、RSAをはじめとする多くのコンピュータ暗号が安全である
ことを保障しているため、もしこれが事実であった場合、コンピュータ暗号の世界に多大な
影響を及ぼすと予想される。

論文は以下のURLからたどることができる。

また、ニューヨークタイムズの記事によると、ベル研のDr. Carl Pomerance博士は
この論文を正確(correct)であると断定し、「このアルゴリズムは美しい。」
("This algorithm is beautiful.")とコメントしたという。

論文のURL(英語: 数学者の写真あり): http://www.cse.iitk.ac.in/news/primality.html
NY Timesの記事(英語): http://www.nytimes.com/2002/08/08/science/08MATH.html
(ユーザ登録(無料)が必要)
リクエスト: http://news2.2ch.net/test/read.cgi/newsplus/1028625378/768

素数判定が簡単に可能でも素因数分解が簡単に可能、ってわけでも
ないらRSAは問題ないのでわ？

これってある意味セキュリティーホールだろ。
こんなに簡単に発表していいのか?

論文の'4.The Algorithm'に書かれてる
13行のソースっぽいの、書き方がおもしろいな。

coprime って何?

誰か完成してみて

function MaxPrime(n:Integer):Integer; //n迄の最大の素数
begin
while not　isPrime(n) do dec(n);
Result:=n;
end;

function isPrime(n:Integer):boolean;
var r:integer
begin
// ( n is of the from a^b,b>1)　って何？
if ( n is of the from a^b,b>1) then
　　 begin Result:=false;exit;end;
r:=2;
while r<n do begin
　if gcd(n,r) then begin Result:=false;exit;end;
　if isPrime(r) then　q:=MaxPrime(r-1);
　if (q >= round(4*sqrt(r)*ln(n)) ) then
　if ( round(power(n,r-1/q)) mod r) then break;
　r:=r+1;
end;
for a:=1 to round(2*sqrt(r)*ln(n)) do
　 // if( (x-a)^n ≠ (x^n-1) (mod x^r -1 ,n)
　if round(power(x-1,n)) mod (power(x,r)-1 ,n) then begin Result:=false;exit;end;
Result:=true;
end;

＞暗号の世界に多大な影響を及ぼす
強い暗号がより簡単に作り出せるっ
てことじゃねーのか？

適当に翻訳。お前ら解説しる！

4 The Algorithm
Input: integer n > 1

1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;
2. r = 2;
3. while(r < n) {
4. if ( gcd(n,r) != 1 ) output COMPOSITE;
5. if (r is prime)
6. let q be the largest prime factor of r - 1;
7. if ( q>= 4*sqrt(r)*log(n) and ( n^((r-1)/q) != 1(mod r) )
8. break;
9. r = r + 1;
10. }
11. for a=1 to 2*aqrt(r)*log(n)
12 if ( (x-a)^n != (x^n -a)*(mod x^n - 1,n)) output COMPOSITE;
13 output PRIME;

相互リンク
数学板
素数判定は「決定的」多項式時間で可能
http://science.2ch.net/test/read.cgi/math/1028813059/

1. if ( n is of the form a^b , b > 1 ) output COMPOSITE; nがa^bの形をしていたら composite 4. if ( gcd(n,r) != 1 ) output COMPOSITE; nとrの最大公約数が1じゃなかったら、composite 5. if (r is prime) 再帰 こんな感じ?

>>18
( n is of the form a^b, b>1 ) # from じゃなくて form
は n が a^b の形で表される数なら以下のアルゴリズムで
誤って prime と判定されてしまうので先に蹴っとけって話じゃないすか。

と英語が苦手でよくわかってもないのにテキトーなことを言ってみるテスト。

>>21
>>9

1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;
nがa^bの形をしていたら composite

4. if ( gcd(n,r) != 1 ) output COMPOSITE;
nとrの最大公約数が1じゃなかったら、composite

5. if (r is prime) 再帰
こんな感じ?

俺がリアル厨房の時に作ったポケコン用の素数判定プログラムは遅かったなぁ（ｗ
なんとかのふるいそのまんま。２以外は６の倍数±1だけでチェックするようにしてた。

　γ~三ヽ
　(三彡０ﾐ)
　（　´∀｀） 　＜じゃあ漏前ら、まずnがa^b の形をしているかどうかを
　（_つノﾉｌ|つ 　　調べる方法を教えろ。
　 Lｌ_|_|_ｌ.||
　（_＿）＿）

誰かＣに直してけれ・・・

> 5. if (r is prime) 再帰
> こんな感じ?

なんで再帰?
どこにそんなこと書いてあんのよ?

>>25
エラトステネスのふるい？

function MaxPrime(n:Integer):Integer; //n迄の最大の素数
begin
　while not　isPrime(n) do dec(n);
　Result:=n;
end;

function isPrime(n:Integer):boolean;
var r:integer
begin
Result:=false;
if isCanPowerAofB(n) then exit; //もし n=a^bの形に出来るなら素数ではない
r:=2;
while r<n do begin
　if gcd(n,r) >1 then exit; //最大公約数が1以外に存在するなら素数ではない
　if isPrime(r) then　q:=MaxPrime(r-1); //rが素数なら qをr-1迄の最大の素数とする
　if (q >= round(4*sqrt(r)*ln(n)) ) then
　if ( round(power(n,(r-1)/q)) mod r) then break;
　r:=r+1;
end;
for a:=1 to round(2*sqrt(r)*ln(n)) do
　 // 12 if( (x-a)^n ≠ (x^n-1) (mod x^r -1 ,n)　あとこの行を
　if round(power(x-1,n)) mod (power(x,r)-1 ,n) then exit;
Result:=true;
end;

よし！
とりあえずお前ら、この12行のソースをCに変換しようぜ！
まず言い出しっぺの俺は
2. r = 2;
9. r = r + 1;
この2行を翻訳しておくよ。

>>28
素数判定の関数の中で is primeって言ってるんだから
再帰で実装しようって発想が一番自然だと思うが.

>>29
そう、それ。

なんか結局途中で素因数分解が要求されてるような気がする。

#include <math.h>

typedef enum {
false = 0,
true = (!false)
} boolean;

int getMaxPrime(int n)
{
while(isPrime(n) != true) {
n--;
}

return n;
}


boolean isPrime(int n)
{
if (isCanPowerAofB(n)) {
return false;
}

int r = 2;

while (r < n) {
if (gcd(n,r) != 1) {
return false;
}

if (isPrime(r)) {
int q := MaxPrime(r-1);

if (q >= round(4*sqrt(r)*ln(n))
&& round(pow(n,(r-1)/q)) mod r) {
break;
}
}

r++;
}

for (int a = 1 ; a <= round(2*sqrt(r)*ln(n)) ; a++) {
if (round(pow(x-1,n)) mod (pow(x,r)-1 ,n)) { // (*)
return false;
}
}

return true;
}

/*
* (*)のところは,
* if ( (round(pow(x-1,n)) % (pow(x,r)-1 ,n)) == 0) {
* でいいんかな?
*/

TABでじさげをして見る。
再帰というより単なるループやね。
integer n > 1
　1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;
　2. r = 2;
　3. while(r < n) {
　4. 　　if ( gcd(n,r) != 1 ) output COMPOSITE;
　5. 　　if (r is prime)
　6. 　　　　let q be the largest prime factor of r - 1;
　7. 　　　　if ( q>= 4*sqrt(r)*log(n) and ( n^((r-1)/q) != 1(mod r) )
　8. 　　　　　　　break;
　9. 　　r = r + 1;
　10. }
　11. for a=1 to 2*aqrt(r)*log(n)
　12. 　　if ( (x-a)^n != (x^n -a)*(mod x^n - 1,n) ) output COMPOSITE;
　13. output PRIME;

おまいら 12行目の x が何だかわかっているのか？

　γ~三ヽ
　(三彡０ﾐ)
　（　´∀｀） 　＜さっさとnがa^b の形をしているかどうかを
　（_つノﾉｌ|つ 　　調べる方法を教えろ。
　 Lｌ_|_|_ｌ.|| 　　　あと最大公約数を求める方法とな。
　（_＿）＿）

最大公約数はユークリッドの互割法で解けたと思ふ。

> nがa^b の形をしているかどうか
これ、難しそうだな。当然aは素数、ということなのか？

　　　　　　　　　　　　γ~三ヽ
　　　　　　　ｶﾁｬ　 　(三彡０ﾐ)
　　　( ﾟдﾟ)　　;y=ｰ　（　´∀｀）･∵.　ﾀｰﾝ
　 　 (|　y |＼／　　　（_つノﾉｌ|つ
　　　　　　　　　　　　

途中のループの

while r<n do begin
　if gcd(n,r) >1 then exit; //最大公約数が1以外に存在するなら素数ではない
　if isPrime(r) then begin
　　q:=MaxPrime(r-1); //rが素数なら qをr-1迄の最大の素数とする
　　if (q >= round(4*sqrt(r)*ln(n)) ) then
　　if ( round(power(n,(r-1)/q)) mod r) then break;
　end
　r:=r+1;
end;

これって全数検査してない？

>>38
for a in any primes
　m ← n
　while (m mod a) = 0
　　m ← m / a
　　if m = 1 output TRUE
output FALSE

>>37
分かりません。どっから出てきた（ｗ
論文英語だし。
（おそらく日本語でも理解できそうにもないぞ）

誰か論文読むの速いヤシ、かもーん！

>>42
a in any primesって…ど、どうしろと.

>>37
x=a=2と置け

#include <math.h>
typedef enum { false = 0, true = (!0) } boolean;

int gcd(int a, int b) {
int c;
while (b != 0) {
c = a % b;
a = b;
b = c;
}
return a;
}

boolean isPrime(int n)
{
int r = 2;
int a = x = 2;

if (isCanPowerAofB(n)) {
return false;
}

while (r < n) {
if (gcd(n,r) != 1) {
return false;
}

if (isPrime(r) == true) {
int q = MaxPrime(r-1);
if (q >= round(4*sqrt(r)*ln(n))
&& (round(pow(n,(r-1)/q)) % r) == 0) {
break;
}
}
r++;
}

for (a = 1 ; a <= round(2*sqrt(r)*ln(n)) ; a++) {
if ((round(pow(x-1,n)) % (pow(x,r)-1 ,n)) == 0) {
return false;
}
}

return true;
}

int getMaxPrime(int n)
{
while(isPrime(n) != true) {
n--;
}

return n;
}

結論：偏差値４０の高学歴の私が理解できないのでインチキです。

>>45
頭いー
a^bは１ビットだけ立ってるか判定し、(x-a)=0で計算するのか・・・

>>44
だからこれ、途中までの素数の表を持っておくか、再帰するかしないとダメな
んじゃないかと。

偏差値と学歴は関係ない。

　　　　　　　　　　インド人のおっさんよぉ･･･
　　　　　　　はじめっからCなり何なりでコードかけよ。なぁ･･･
　　　　　　　　　　　　　　　
　　　　　　 ∧ 　 　　　　 　∧ 　 　　　　　　 ∧
　 　 　 　 /　ヽ　　　　　　/　ヽ_　　　　　　 / .∧
　　　　　/　　 ｀､　　　＿/　　 ｀､⌒ヾ⌒ヽ/　　∧
　　　 ／　　　 　 ￣￣／　　u (.....ノ(....ノ　　　／ ヽ
　 　 l:::::::::　　　　　 　 |　　　　　　　　　 　u　.:（....ノノ
　　 |:::::::::: 　-=・=-　/￣￣ヽ　　　　　　　 ::::::::::::::／`ヽ
　　 .|:::::::::::::::::　 ＼_(＿＿_..ノ　　　u　 ::::::::::::::::::::(....ノノ
　 　 ヽ::::::::::::::::::: 　＼／ヽ　　u 　　 ::::::::::::::::::::::::::::ノ

論文の世界ではPascalちっくに書くのがおしゃれなのれふ。

8086アセンブリ言語で書いてあるとｶｺｲｲのに

　　　　　　　　　　　コピペで即コンパイルオッケーなコード
　　　　　　　　　　　　　　書けぇ言うとんじゃあ･･･

　　　　　　 ∧ 　 　　　　 　∧ 　 　　　　　　 ∧
　 　 　 　 /　ヽ　　　　　　/　ヽ_　　　　　　 / .∧
　　　　　/　　 ｀､　　　＿/　　 ｀､⌒ヾ⌒ヽ/　　∧
　　　 ／　　　 　 ￣￣／　　u (.....ノ(....ノ　　　／ ヽ
　 　 l:::::::::　　　　　 　 |　　　　　　　　　 　u　.:（....ノノ
　　 |:::::::::: 　-=・=-　/￣￣ヽ　　　　　　　 ::::::::::::::／`ヽ
　　 .|:::::::::::::::::　 ＼_(＿＿_..ノ　　　u　 ::::::::::::::::::::(....ノノ
　 　 ヽ::::::::::::::::::: 　＼／ヽ　　u 　　 ::::::::::::::::::::::::::::ノ

>>35-36
> if (round(pow(x-1,n)) mod (pow(x,r)-1 ,n)) { // (*)
> 12. 　　if ( (x-a)^n != (x^n -a)*(mod x^n - 1,n) ) output COMPOSITE;

そこは
(x-a)^n % (x^r - 1) != (x^n - a) % (x^r - 1)
&& (x-a)^n % n != (x^n - a) % n
って意味じゃないのか?

>>54
環境もってるやつきぼ〜ん
http://science.2ch.net/test/read.cgi/math/1028813059/38

>>45
xの多項式の係数を全部比較するんだよ
xに値を代入してどうするんだよ

もう書き込めないっぽ…行数が….
int gcd(int a, int b) {
int c;

while (b != 0) {
c = a % b;
a = b;
b = c;
}

return a;
}

boolean isCanPowerAofB(int n) {
int i;
for (i = 0 ; i < sizeof(int) ; i++) {
if ( ((1 << i) | a) != (1 << i)) {
return false;
}
}
return true;
}

boolean isPrime(int n)
{
int r = a = x = 2;

if (isCanPowerAofB(n) == true) {
return false;
}

while (r < n) {
if (gcd(n,r) != 1) {
return false;
}

if (isPrime(r) == true) {
int q = MaxPrime(r-1);

if (q >= round(4*sqrt(r)*ln(n))
&& (round(pow(n,(r-1)/q)) % r) == 0) { // modの処理あってる?
break;
}
}
r++;
}

for (a = 1 ; a <= round(2*sqrt(r)*ln(n)) ; a++)
if ((round(pow(x-1,n)) % (pow(x,r)-1 ,n)) == 0)
return false;

return true;
}

int getMaxPrime(int n)
{
while(isPrime(n) != true) n--;
return n;
}

>>56
　　　　　　　　　　　MATLABなんぞ持っとるか
　　　　　　　　　　　　　　おんどりゃぁ･･･

　　　　　　 ∧ 　 　　　　 　∧ 　 　　　　　　 ∧
　 　 　 　 /　ヽ　　　　　　/　ヽ_　　　　　　 / .∧
　　　　　/　　 ｀､　　　＿/　　 ｀､⌒ヾ⌒ヽ/　　∧
　　　 ／　　　 　 ￣￣／　　u (.....ノ(....ノ　　　／ ヽ
　 　 l:::::::::　　　　　 　 |　　　　　　　　　 　u　.:（....ノノ
　　 |:::::::::: 　-=・=-　/￣￣ヽ　　　　　　　 ::::::::::::::／`ヽ
　　 .|:::::::::::::::::　 ＼_(＿＿_..ノ　　　u　 ::::::::::::::::::::(....ノノ
　 　 ヽ::::::::::::::::::: 　＼／ヽ　　u 　　 ::::::::::::::::::::::::::::ノ

たとえ、実行ファイルが出来たとして
どういう方法で何がわかるのだろうか･･･。

大学のPCに入ってたな〜>>MATLAB
休み明け待つ前までには和訳した方が早そう

小さい値で素数判定がキチンとできてるかを確認して,
あとは適当に大きな値で速度計算…かな.

ネタが混じり始めた・・・どれが本当かわかんない（鬱

>>60
素数クイズ〜この数字は素数？


・・・みたいな。

結局12行目のxって何?

とことんデカイ素数が出てきて楽しそうですね。

>>55
ｽﾏﾝ、書いている意味がもはや分からん・・・。
どこから&& and が出てくるんだ？
それと
12. 　　if ( (x-a)^n != (x^n -a)*(mod x^n - 1,n) ) output COMPOSITE;
これは
12. 　　if ( (x-a)^n != (x^n -a)*(mod x^r - 1,n) ) output COMPOSITE;
間違いれした。

>>65
多項式の変数

結局

このアルゴリズムによる素数判定の計算速度＜量子コンピューターによる素数判定の計算速度

でいいの？

>>68
つまり、12行目は多項式(x-a)^nと多項式(x^n -a)*(mod x^r - 1,n)の係数が
等しくない時ということ?

>>65
ｴｯｸｽ

なんとなく適当なことを書き込んでみるテスト。
単純な素数判定だとr=2から初めてsqrt(n)まで順番に割れるか
調べるんだけど、この方法だとlog(n)まで調べればOK,と言ってるのかな？

違ってたらｿﾏｿ

http://www.cybernet.co.jp/matlab/download/#trial
ほれ、MATLABトライアル版。
しかし、３０日ではあまり大きな素数の判定が出来ないという罠。

>>70
多項式 (x-a)^n - (x^n -a) を多項式 x^r - 1 で割った余りの多項式の係数が
どれか１つでも n で割り切れないということ

と思う

(x-1)^2= x^2 -2x +1 で1次の項が2で割り切れる。
(x-1)^3= x^3 -3x^2 + 3x -1 で1次と2次の項の係数が3で割り切れる。
(x-1)^4= x^4 -4x^3 + 6x^2 -4x +1 は2次の項の係数6は4で割り切れない。
4は素数ではない。
(x-1)^5= x^5 -5x^4 + 10x^3 -10x^2 +5x -1 の1次から4次の項の
係数はすべて5で割り切れる。

nを与えられたらnと互いに素な数aを取って
多項式(x-a)^nの1次から(n-1)次までの係数がすべてnで割り切れて
a^nをnで割った余りがaならばnは素数

でもこのやりかたではn次の多項式の係数を計算しなければならず大変
よって小さい数rをうまくとって
x^rは1とする計算を間に入れてr次の多項式の計算に収めればよい。
このrの候補の取り方が最初のwhile文。
このrは小さい数ですむ というのがLemma4.2の主張。
チェックaの候補もrが小さいので少しの候補ですむ。

r次以下の多項式(x-a)^rの係数の計算はFFTを使えばよいのだろう。

8ページ目には予想として、この判定は
このaは1だけのチェックでよく、
rはn^2-1の約数ではないという条件だけでよいのではないか
といっている。

>>76
詳しい説明Thx.
(x-a)^nって2項定理？だよね。素数判定が絡んでいたなんて意外。

> x^rは1とする計算を間に入れてr次の多項式の計算に収めればよい。
この1文がよく分かりまへん・・・。

>>77
r=3として例をあげると
x^3は1にしてx^4はxにしてx^5はx^2にしてx^6は1にする。
x^5 +3x^4 +2x^3 +4x^2 +2x +3 ≡
x^2 +3x +2 +4x^2 +2x +3 = 5x^2+5x+5 (mod x^3-1)
これならどんな多項式も2次以下の多項式になる。
だからいつもr次以下の多項式計算だけですむ。
係数の無限長整数変数はr個だけですむ。

素数判定がＰで因数分解がＮＰなら、「合理的な時間で完全な暗号が作れることになりますた。」
というとてもおめでたい発表だと思うのだが。

>>79
と言うかそう言うことだと思うのですが。
でも何故か世間的には暗号があぼーんらしいです。世間は広いです。

>>79
素因数分解の困難さに基づく暗号が、素因数分解を用いる以外の手段で解読されない事を
示さないと完全ではない罠。

>>81
それは今回の件とは関係が無いような…

RSAも現実的な時間で解読できるようになるのか？

>>81 NTTのEPOCとか。

>>82
いや、あくまで79に対してのレス。素因数分解がNPだとわかったとしても
RSAの安全性は証明されないわけで。

スレタイどうにかならへん〜？
まるでこの板の住民がアレみたいだ。

>>85
了解です。
でも本当にRSAの堅牢性が（ロジックレベルで）否定される日が来たらいろんな意味で。凄いですよね。

ああ、失礼。たしかにそうだね。

ところで、ＲＳＡが因数分解と同程度に難しいっていうのは証明済みなんだっけ？

おしえて。

>>72みたくsqrt(n)まで割って確かめるのでも既に○(sqrt(n))なんで多項式時間じゃないの？
多項式時間ってなに？

MATLAB のかわりに Octave でもええんちゃうん？
いや、ソース見てないんでなんともいえないけど。

>>89
nを入力とするとき、nの桁数（=O(log(n)）の多項式で
抑えられるのが多項式時間。

実行時間が sqrt(n) だと O(exp(log(n)))なので指数時間。

ニュー速＋は結構盛り上がってるね

>>90
octave, １行目からparseエラーでした。
俺の使い方が悪いのか、octaveが対応してないのか・・・

>>85
禿同ﾊｧﾊｧ

>>88
素因数分解ができればRSAは解読できる。
RSAが解読できると素因数分解ができるかどうかはわかっていない。

つまり、素因数分解の方がRSAよりやさしい問題でない
ことは分かっている。

楕円暗号は大丈夫なんだよな?

こういうプログラムを書くには、JavaのBigInteger クラスが便利だよ！
gcd とか、剰余群上でのべき乗とかまさにうってつけな演算がてんこ盛りだから。

BigIntegerをC++のクラスライブラリとして実装ｼﾙ！

つーか、かなり恥ずかしいなこのスレのタイトル。
バカ丸出しだね。

>>91
うーん、多項式って

a_1 x^1 + a_2 x^2 + ... a_n x^n

だと思ってたんだけど。。。
それにexp(log(n))ってnだから計算時間がsqrt(n)だと計算量はO(n)ってこと？？？

　　　　　　 　 　 　 　 　 　 /　ヽ　　　 　 　 /　ヽ
　　　　　　　　　　　　　　 /　　　ヽ＿＿＿/　　　ヽ
　　　　　　　　　　　　／　　　井＼　　l＿＿＿l　／＼
　　　　　　　　　　 　 |　　井　　 ● 　|　　　 |　　●　 |　　 ／￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　　へ　　　 |　　 へ 　 　 　 ヽ 　 /　　　　　|　＜　Cのソースまだー？
　　　　　　　 ＼＼　　＼　 ＼＼　　　　ヽ/　　　　 ／ 　　＼＿＿＿＿＿＿＿＿＿＿＿＿
ﾁﾝ　　　　　　　 ＼＼　　.＞　＼＼　　　　　　　　　　ヽ
　　　ﾁﾝ　　　　　　＼＼/　　　　＼＼　　＿　　　　　　 |
　　　　　　＼￣￣￣￣￣￣￣／　 /￣　　 ヽ　　　　/　　 ＿
　　　　　　　 ＼回回回回回／￣￣ヽ　　　　　　　　/￣￣ ／|
　　　　　　　　　＼＿＿＿／　　　　　 ヽ＿＿＿＿／　　／　 |
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 ／　　　|
　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ／　　　　 |

>>100
計算量はO(√n)
√n=exp(1/2 * log n)だからlog nの指数

xの多項式は
a_0 + a_1 x + a_2 x^2 + ... + a_n x^n
であなたのいうとおり。
多項式時間の多項式とは、nの桁数を表すlog n について多項式ということ。
a_0 + a_1 log n + a_2 (log n)^2 + ... + a_n (log n)^m
は(log n)^mのオーダー O((log n)^m)

でO((log n)^12)でできる素数判定が書いてあるみたい

/.j にもスレ^H^Hトピックが立ちました。

>>100
10^20=100000000000000000000
まで調べる場合は平方根が10^10=10000000000,
(log10)だと20
計算量の違いは歴然なのれす。

>>102
まだわかんにゃいなー
n^k = exp(k log n)だから多項式の各単項は全部指数になっちゃうんきがするんだにゃー

>>101
これは無限長整数変数を使って、掛け算も高速乗算法で
カリカリに書いて多項式(x-a)^nの係数の計算を
r次に畳み込んで計算しないといけない。
rを求めるwhileループはO( log^9 n)しかかからないからといって
r-1の最大素因子qを求めるところを√rから2までの数で割って求めていたりするから
Cで書いたとしても速く動くというものでもない。

実用では8ページの予想
rはnの約数でもなくn^2-1の約数でもない数にしておいて
aは1だけをチェックするだけで素数判定できるだろう
という擬判定にしておいたらいいのでは。

>>102
何がわかんないかというと
O(√n)のnはlog n = N にしてあげないのに多項式の n は log n = N にしちゃってることなんだにゃ

もう先生どっかいっちゃたみたいけど最後にも一つしつみょんしておれも帰る。
多項式時間の

a_k x^k

の x が log n の事ってのははじめて聞いたので、参考書知りたいにゃ。

>>78
亀レスｽﾏｿ
> x^3は1にしてx^4はxにしてx^5はx^2にしてx^6は1にする。
> 係数の無限長整数変数はr個だけですむ。

x^3を1としてmodを取っても破綻をきたさない、というのは知られた定理
でいいのれすか？

この論文の主題は最初にrという（比較的小さな）数を短時間に
見つけて、それを既存？の素数判定法に還元できた、ということ
なのでせうか？

　　　　　　 　 　 　 　 　 　 /　ヽ　　　 　 　 /　ヽ
　　　　　　　　　　　　　　 /　　　ヽ＿＿＿/　　　ヽ
　　　　　　　　　　　　／　　　井＼　　l＿＿＿l　／＼
　　　　　　　　　　 　 |　　井　　 ● 　|　　　 |　　●　 |　　 ／￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　　へ　　　 |　　 へ 　 　 　 ヽ 　 /　　　　　|　＜　std::valarray使ったの、まだー？
　　　　　　　 ＼＼　　＼　 ＼＼　　　　ヽ/　　　　 ／ 　　＼＿＿＿＿＿＿＿＿＿＿＿＿
ﾁﾝ　　　　　　　 ＼＼　　.＞　＼＼　　　　　　　　　　ヽ
　　　ﾁﾝ　　　　　　＼＼/　　　　＼＼　　＿　　　　　　 |
　　　　　　＼￣￣￣￣￣￣￣／　 /￣　　 ヽ　　　　/　　 ＿
　　　　　　　 ＼回回回回回／￣￣ヽ　　　　　　　　/￣￣ ／|
　　　　　　　　　＼＿＿＿／　　　　　 ヽ＿＿＿＿／　　／　 |
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 ／　　　|
　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ／　　　　 |

今までの解説を読んで書き直し。

integer n > 1
　1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;// n がa^b で表せるか確認する。
　2. r = 2;// r = 2 から一つずつ調べていく。
　3. while(r < n) {
　4. 　　if ( gcd(n,r) != 1 ) output COMPOSITE;// n,r の最大公約数が1でないか？
　5. 　　if (r is prime)// rが素数の場合
　6. 　　　　let q be the largest prime factor of r - 1;// r-1 の最大の素数、qを探す
　7. 　　　　if ( q>= 4*sqrt(r)*log(n) and ( n^((r-1)/q) != 1 (mod r) ) // 後半はrで割った余りが1でなければ
　8. 　　　　　　　break;
　9. 　　r = r + 1;
　10. }// 最初のループを抜けて、次の一定回数のループで多項式を割った場合の余りを求める。
　11. for a=1 to 2*aqrt(r)*log(n)
　　　　　// x^n-1 で (x-a)^n を割った余りが x^n-a になるか？
　12. 　　if ( (x-a)^n != (x^n -a) (mod x^n - 1,n) ) output COMPOSITE;
　13. output PRIME;

Cで書く際の難点は
　1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;// n がa^b で表せるか確認する。
　4. 　　if ( gcd(n,r) != 1 ) output COMPOSITE;// n,r の最大公約数が1でないか？
　6. 　　　　let q be the largest prime factor of r - 1;// r-1 の最大の素数、qを探す
　12. 　　if ( (x-a)^n != (x^n -a) (mod x^n - 1,n) ) output COMPOSITE;
この４つと思われ。
このうち4.は簡単。
6.もダサいルーチンなら書ける。
面倒そうなのは12.>>106が何やら詳しそうだが力技でなんとかなりそう。
1.は全然想像もできん。お前ら数学の定理かなんか知ってたら教えてくり。

ムーアの法則通り　5年で性能は10倍になった
　CPUは20GHz相当だし
　RAMは2GByte
　HDDは1Tに

でも、この性能何に使えばいいのよ？

>>108
なぜｘがlog n なのかというと、もともと
素因数分解の判定問題が判定したい数 n の桁数
に対して多項式時間で解けるかという問題を考えて
いるからです。

>>109
はい、言い方を代えるとx^3-1で割った余りの2次式にしているだけですから。
x^5 +3x^4 +2x^3 +4x^2 +2x +3 をx^3-1で割った余りが5x^2+5x+5のはずです。

このうまく工夫されたrを見つけて
a=1から2√r log n まですべてチェックすると
必ず素数判定できる ということ。
このrの見つけ方とaの範囲がうまく押さえられているから
多項式時間でできることがわかった ということだと思うよ。

こちらもまだ全部チェックしているわけではないのでスマソ

　　　　　　　　　　さっさとCのコード･･･
　　　　　　　ｶﾁｬ￣￣￣∨￣￣￣￣￣
　　　( ﾟдﾟ)　　;y=ｰ （　｀д´）･∵.　ﾀｰﾝ
　 　 (|　y |＼／　　 （_つ 　 つ
　　　　　　　　　　　　

ヤフーオークションで、凄い人気商品、発見！！！

プランテック製の「 RX-2000�V 」を改造済み
にした、アイティーエス製の「 RX-2000�V 」↓
http://user.auctions.yahoo.co.jp/jp/user/NEO_UURONNTYA#.2ch.net/

ヤフーオークション内では、現在、このオークション
の話題で、持ちきりです。

ヤフー ID の無い方は、下記のホームページから、
購入出来る様です↓
http://www.h4.dion.ne.jp/~gekiyasu/#.2ch.net/

　　　　　　 　 　 　 　 　 　 /　ヽ　　　 　 　 /　ヽ
　　　　　　　　　　　　　　 /　　　ヽ＿＿＿/　　　ヽ
　　　　　　　　　　　　／　　　井＼　　l＿＿＿l　／＼
　　　　　　　　　　 　 |　　井　　 ● 　|　　　 |　　●　 |　　 ／￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　　へ　　　 |　　 へ 　 　 　 ヽ 　 /　　　　　|　＜　Fortranに書き直したのまだー？
　　　　　　　 ＼＼　　＼　 ＼＼　　　　ヽ/　　　　 ／ 　　＼＿＿＿＿＿＿＿＿＿＿＿＿
ﾁﾝ　　　　　　　 ＼＼　　.＞　＼＼　　　　　　　　　　ヽ
　　　ﾁﾝ　　　　　　＼＼/　　　　＼＼　　＿　　　　　　 |
　　　　　　＼￣￣￣￣￣￣￣／　 /￣　　 ヽ　　　　/　　 ＿
　　　　　　　 ＼回回回回回／￣￣ヽ　　　　　　　　/￣￣ ／|
　　　　　　　　　＼＿＿＿／　　　　　 ヽ＿＿＿＿／　　／　 |
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 ／　　　|
　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ／　　　　 |

>>111
1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;// n がa^b で表せるか確認する。
はよくわからないね。
7ページ目のTheorem5.1の証明の最初に
The first step of the algorithm takes asymptotic time: O(log^3 n).
とあるがどうするのだろう？
べき数であるかどうかの判定法はどうするのかなぁ

106だけど具体的なアルゴリズムは知らんので私には書けないよん。

>>117
いらねーよ。

そういやWindows用のFortranもあまり聞かないな。

彡 　　　ﾋﾞｭｳｳｳ…
　　　　　　　　　　彡
　　彡　　　　　　　　　> n がa^b で表せるか確認する。
　　　　　　　 .∧ ∧ 　
　　　　　　 ヾ(,,ﾟДﾟ),)　これを攻略できるひとはいずこ･･･
　　　 　 　 人つゝ 人,,
　　　　　 Ｙノ人　ノ ノﾉゞ⌒〜ゞ
　　　 .　 ノ /ミ|＼､　　　 ノﾉ　（　彡
　　　　 `⌒ 　.Ｕ~Ｕ`ヾ　　　　丿

で、 RSA が破られるわけではないんだよね？

DE*の方が機密性が高いと。

>>120
わかってきた。
nがべき数であるかの判定。
aは2以上だからbは高々log_2 n=log n
b=2からlog_2 nまでnのb乗根を計算しても
累乗根の計算は割り算に毛が生えたぐらいの手間だったはずだから
O((log n)^2)で押さえられるのかもしれない。(ここは怪しい)
よってべき数であるかの判定はO((log n)^3)で
12行目のO((log n)^12)よりはるかに小さいから無視できると。

>>123
なるほろ・・・。
ということは
> 1. n がa^b で表せるか確認する
ここも、素数を調べるルーチン同様、ダサダサの力技で行けばいいのか・・・。

ん！解決したぞ！
じゃお前ら頼むわ（ｗ

よく判らんが、暗号キー１個方式で充分だ。

総崩れつうのは太い間違い。

>>123
んー・・・でもさー
> n がa^b で表せるか確認する
これってa^2のケースを考えると、
sqrt(n)の数まで調べなきゃいけないような気がする。

ここにも逝って良しの１がでたぞ。いつも通り微弱電波だから無視無視。

おまいら、C++で演算子オーバーロード使ってクラス作ってください。

>>127
b=2のときは、
nの平方根が自然数aになるか判定するだけだから
割り算とほぼ同じ手数でできるよ。

おまえら、そんなに素数判定したいか？

アホアホうるせえな。
バカでも食いつきやすいように、分かりやすくセンセーショナルに
タイトルつけたんだよ。
わかっててやったの！
ばーか。

>>130
Σ（ﾟдﾟlll）ｶﾞｰﾝ
すげー速いじゃん。逝ってきます。

>>132
偽者お疲れ

#!/usr/bin/perl-s
$f=$d?-1:1;$D=pack('C*',33. .86);$p=shift;
$p=~y/a-z/A-Z/;$U=~s/( . *)U$/U$1/;
$D=~s/U( . )/$1U;';($V=$U)=~s/U/V/g;
$p=~s/[A-Z]/$k=ord($&)-64,&e/eg;$k=0;
while(<>){y/a-z/A-Z;y/A-Z//dc;$o.=$_}$o.="X"
while length ($o)%5&&!$d;
$o=~s/.chr(($f*&e+ord($&)-13)%26+65)/eg;
$o=~s/X*$//if$d;$o;$o=~s/.{5}/$&/g;
print"$o|n";sub v{$v=ord(substr($D,$_{0}))-32;
$v>53?53:$v}
sub w{$D=~s/(.{$_{0})(.*)(.)/$2$1$3}}
sub e{eval"$U$V$V";$D=~s/(.*)([UV].*[UV])(.*)/$3$2$1/;
&w(&v(53));$k?(&w($k)):($c=&v(&v(0)),$c>52?&e:$c)}

>>134そこ、反応しない

よーし、32ビット版だけど作ってみるぞ。

よーし、じゃパパIA-64あいてにうむ版の最適コード書いちゃおうかな〜。

ゴルゴ１３が守ってくれました。

>>132
全検索しましたが、誰もアホと書いてません。
あなただけです。

>>106 >>78
係数はnで割った余りを格納すればよいので無限長整数でなくても
nが格納できる固定長整数でいい。
nが格納できる固定長整数変数がr個だけでいい。
途中計算は
(x-a)^2,(x-a)^4,(x-a)^8,(x-a)^16,...
と自乗を繰り返すだけだから、
n^2が格納できる固定長整数変数が2r個あればいい。
そして各係数をnで割って余りを出しつつr次以上のm次の係数を
m-r次に加えていけばx^r-1の余りのr次の多項式が得られる。
そして、nを2進展開してその1,0にあわせて
(x-a),(x-a)^2,(x-a)^4,(x-a)^8,(x-a)^16,...
を掛け合わせれば(x-a)^nが得られる。
これをx^r-1で割った余りを係数の足し算で得た後
nで割って余りを出せばよい。
そしてnをrで割った余りの次数のところの係数が1で、
定数項はaで残りの係数は全部0ならよい。

　　　　　　　　∧＿∧
　　　　　　　 （ ´Д｀ ） ＜　よし！もう少しだ！がんばれ >漏前ら
　　　　　　　／,　　/
　　　　　　(ぃ９　　|

すんまそん。力技です。

int is_a_sup_b(unsigned int n) {

  int c, p=0, buf[32] = {0};
  unsigned int i,d;

  while (n && (n & 1)==0) {
    ++buf[p];
    n >>= 1;
  }
  if (buf[p]) ++p;

  i = 2;
  d = 3;
  while (d<=n) {
    while (d<=n && (n % d)==0) {
  ++buf[p];
      n /= d;
    }
    if (buf[p]) ++p;
    d += i;
    i = 6 - i; // 4 と 2 を交互に
  }

  if (n != 1)
    ++buf[p++];

  c = buf[--p];

  while (p--) if (buf[p] != c) return 0;

  return 1;
}

a の b 乗の形であらわせるか？というのを求めます。
ただしaとbが具体的に何なのかは，んーと，簡単に分かるけど
ここでは求めてません。
あんまし試してないんで，検証よろしくです。

考え方はこう。
a^b は，素因数分解すると登場する因数の回数が揃ってるんですよね。
例えば 14^3 = 2744 は 2 * 2 * 2 * 7 * 7 * 7 で
2 も 7 も 3 回登場しますもんね。

#・・・今みんなが悩んでるのはここじゃないという罠？

　　　　　　　　∧＿∧
　　　　　　　 （ ´Д｀ ） ＜　よし！コードが出てきた！検証は任せる >漏前ら
　　　　　　　／,　　/
　　　　　　(ぃ９　　|

>>143
それではnの素因数分解だできてしまっているのでは？

コードは簡潔にしる！
高水準ライブラリを使いしる！

# すいません，今気付きました
# 遅いから使いものにならないという罠・・・

>>145
うん。できてしまってます。
参考文献は「C言語による最新アルゴリズム事典」。

では私はgcd関数をちょいと。

// ユークリッドの互除法で最大公約数を求める。再帰版
int gcd(int n, int r)
{
if ( r == 0 ) return x;
else return gcd(r, n % r);
}

>>144
お前さっきから何もやってねえじゃん。

　　　　　　 　 　 　 　 　 　 /　ヽ　　　 　 　 /　ヽ
　　　　　　　　　　　　　　 /　　　ヽ＿＿＿/　　　ヽ
　　　　　　　　　　　　／　　　井＼　　l＿＿＿l　／＼
　　　　　　　　　　 　 |　　井　　 ● 　|　　　 |　　●　 |　　 ／￣￣￣￣￣￣￣￣￣￣￣￣
　　　　　　　へ　　　 |　　 へ 　 　 　 ヽ 　 /　　　　　|　＜　HSPに書き直したのまだー？
　　　　　　　 ＼＼　　＼　 ＼＼　　　　ヽ/　　　　 ／ 　　＼＿＿＿＿＿＿＿＿＿＿＿＿_
ﾁﾝ　　　　　　　 ＼＼　　.＞　＼＼　　　　　　　　　　ヽ
　　　ﾁﾝ　　　　　　＼＼/　　　　＼＼　　＿　　　　　　 |
　　　　　　＼￣￣￣￣￣￣￣／　 /￣　　 ヽ　　　　/　　 ＿
　　　　　　　 ＼回回回回回／￣￣ヽ　　　　　　　　/￣￣ ／|
　　　　　　　　　＼＿＿＿／　　　　　 ヽ＿＿＿＿／　　／　 |
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 ／　　　|
　　　　　　　　　　　　　　　　　　　　　　　　　　 　　 ／　　　　 |

「多項式時間」ってなんだ？

　　　　　　　　∧＿∧
　　　　　　　 （ ´Д｀ ） ＜　>>150 漏れに何ができるって言うんだ！
　　　　　　　／,　　/
　　　　　　(ぃ９　　|

>>143 早速バグ発見
例に出した数値 2744 からして a^b だと認めてくれないです（笑い

まだ。

>>152
「気合入れれば、力技でいける」の意

HSPに書き直して何に使う気よ？

>>154 で見つけたバグを早速fix
  i = 6 - i; // 4 と 2 を交互に
の行をコメントアウトすればｲｯﾊﾟﾂですた。
でもできるだけ効率的に素数を探しながら因数分解したいんで
改良しなきゃ〜・・・

ともかく>>143はマトモに素因数分解してるのでネタということで。
んーと，a^b であるか否かを判定するのは P 問題なんですか？

　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿＿＿＿＿＿＿
|∴/= ♀=| <漏前ら寝るんじゃねぇ
＼| 　 ▽/　 ￣￣￣￣￣￣￣￣￣
　　￣￣

あーもう頭がアレになってきた
私は眠いので寝ます・・・

途中。変数の宣言なし。
今から多項式の割り算をやってみる。

// n がa^b で表せるか確認する。b > 1
int check_powAB(int n)
{
　　for (a=2;a<=sqrt(n);a++) {　　// 大手抜き。
　　　　for (b=2;b<n;b++) {
　　　　　　m = pow(a,b);
　　　　　　if ( m == n ) return 1;
　　　　　　if ( m > n ) break;
　　　　}
　　}
　　return 0;
}

// rが素数の場合 1を返す 「素数 "列挙" アルゴリズムを極めるスレ」から。
int isPrime(int r)
{
　　int i,z;

　　for (i=1; z=++i; ) {
　　　　while(i%--z)
　　　　　　;　　
　　　　if ( z == 1 ) return 1;
　　}
　　return 0;
}

// r の最大の約数、qを探す
int FindLargestPrime(int r)
{
　　m = (int)sqrt(r);
　　for ( ; m==1; m-- ) {
　　　　if ( r % m == 0 ) return m;
　　}
　　printf("Error\n");
　　exit(0);
}

>>159
>>123にあります。

お前らちゃんと13行で(省略)

というか1行目で指数時間使ってしまったら
もうどうやっても多項式時間で計算できないだろ。

whileループの中ではrは小さいから
rの素数判定とr-1の最大素因子qを求めるところは指数時間でもいいのだけれど。

>>162
int check_powAB(int n)
{
（ 略）
m = pow(a,b);
if ( m == n ) return 1;
if ( m > n ) break;

これはとても危険でし。
次のようにでもしないと。

const double eps = 0.001;
m = (int)(pow(a,b) + eps);
（以下略）

同様に、FindLargestPrime()の
m = (int)sqrt(r);
も
m = (int)(sqrt(r) + eps);
とかしないと。

素数判定ソフトまだ〜？
￣￣￣￣V￣￣￣￣￣
　　　　 ∧＿∧
　　　　（ ･д⊂ヽ゛
　　　　/　　 　_ノ⌒⌒ヽ.
　(￣⊂人　　//⌒　　 ﾉ
⊂ﾆﾆﾆﾆﾆﾆﾆﾆニニニニﾆ⊃

☆ ﾁﾝ　　　　　　　　ﾊﾗﾍｯﾀ〜
　　　　　　ﾊﾗﾍｯﾀ〜
☆　ﾁﾝ　　〃　Λ＿Λ 　 ／￣￣￣￣￣￣￣￣￣￣￣￣
　ヽ　＿＿_＼（＼・∀・）＜　神様の再臨まだー？？
　 　 ＼＿／⊂　⊂＿)＿ ＼＿＿＿＿＿＿＿＿＿＿＿＿
　 ／￣￣￣￣￣￣￣／|
　　| ￣ ￣￣￣　￣￣:| :|
　　|　　　　　　　　 　　 |

>>167
神様は寝ました。

>>167-168
　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿＿＿＿＿＿
|∴/= ♀=| <漏前らは寝てよし！
＼| 　 ▽/　 ￣￣￣￣￣￣￣￣
　　￣￣

これって神帝人生たんがすでに証明してたのでは？

　　　　　　　　　　　　　　☆ ﾁﾝ
　　　 　 　 ☆　ﾁﾝ　　〃　∧＿∧ 　　／￣￣￣￣￣￣￣￣￣￣￣￣
　 　 　 　 　　ヽ　＿＿_＼（＼・∀・）＜　JavaScriptに書き直したのまだぁ〜？
　　 　 　 　 　 　 ＼＿／⊂　⊂＿)＿ ＼＿＿＿＿＿＿＿＿＿＿＿＿
　　 　 　 　 　 ／￣￣￣￣￣￣￣／|
　　　　　　　　| ￣ ￣￣￣￣￣￣:|　:|
　　　　　　　　|　　　　　　　 　 　 　|／

while (1) cout<<"\t\b\b (・∀・)ﾏﾝｺｰ"<<endl;

後でpascalに書き直してくれるとありがたい…ダメですか。

>>174
ノノの脳内にPascal→C++翻訳機がありますがFortran→Pascalはちょっと･･･
品切れれす(　´�D｀)

>>152
アルゴリズム A に対して、多項式関数 p と正整数 N が存在し、任意の
サイズ n (> N) の入力を与えたときにアルゴリズム A が常に p(n) 以下
の実行時間で終了するとき、A を多項式時間アルゴリズムと言う。

サイズは入力を表すのに必要なビット数（自然数なら桁数）、実行時間は
アルゴリズムのステップ数と考えとけ。

（厳密にはチューリングマシンを使って定義する）

namco

swap
↓  ↓
n a m c o

m a n c o

manco

(・∀・)ﾏﾝｺｰ

ニュー速＋よりはまともな住人が多いことが確認できただけでもよしとしよう。

>>178
> (・∀・)ﾏﾝｺｰ
の次でそんな事言われてもなー

スマソ、

素数判定が多項式時間で可能　->　RSAあぼーん

の論理展開が全く分からんのだが。

今回のは「素因数分解が多項式時間で可能」になったワケじゃないから、
直接はRSAの脆弱性ハケーン、って事にはならないハズだよな。

>>180
髭しくガイシュツ

んー、作ってみたけど、どうもまともに動いてないようです。
もう眠いのでビール飲んで寝まふ。
http://www.geocities.co.jp/Technopolis-Mars/1346/prime.lzh

12行目以外の関数はまともに動いているようなのだけど、
12行目の関数がうまく動きませんでした。

素数を11で調べたとき、
n=11,r=2,q=1
n=11,r=3,q=2
n=11,r=5,q=2
n=11,r=7,q=3
n=11,r=11,q=3
ときて、12行目に入り、
a=1 から a=2*sqrt(11)*log(11) で a=8 までループします。
ここで (x-a)^n の a^n が32bitを超えたので検証できず。
2〜10までは正しく判定してるようです。使えねぇ・・・（ｗ

12行目は>>70の意見
>多項式 (x-a)^n - (x^n -a) を多項式 x^r - 1 で割った余りの多項式の係数が
>どれか１つでも n で割り切れないということ
を採用してます。
>>141の方法を使えばかなり改善できそう？だけど難しすぎて降参しました。

function isCanPowerAofB(n:Integer):boolean; // n=a^bの形になるか
var b:Integer;
var lnN,a:double;
begin
lnN:=ln(n);
Result:=false;
for b:=2 to trunc(lnN/ln(2))do begin
a:=Power(n,1/b);
a:=a-round(a);
if round(a*1000000)=0 then begin result:=True;exit;end;
end;
end;

みなさん寝てるんですか??

仕事してください

>>185
普通の会社は今日は休みです。

>>113
分かった｡ありがとうでした｡
N=nならNの多項式時間でも
N=log n ならNの指数時間ってことだったんすね｡

JDK1.5では素数クラスが含まれます。

素因数分解の一般数体ふるい法（http://www.rkmath.rikkyo.ac.jp/~kida/nfs_intro.pdf)
ってどれぐらいのオーダーですか？

おまいら早くBASICで書き直してくださいよ。
9801で検証するんで。

>>190
あぁ、日本の数学者が作ったUBASICで書かれたなら
9801で検証できるよね。

いずれにせよ、量子コンピュータが普及すれば今の暗号技術は使えなくなる分けであるし、
それもそう遠い未来ではない。

といってみるテスト。

お前ら早く86ネイティブに書き直してくださいよ。
.comファイルで検証するんで。

>>192
近い未来でもないと思うが。多分。

漁師コンピュータが完成するっていうのと、一般に普及するっていうのとでは
極端に実現度が違う。

お前ら早くJavaバイトコードに書き直してくださいよ。
$ Java sosuu
で走らせるんで。

量子コンピュータ?
すでにあるよ。僕らが住んでるこの宇宙がそう。

Bignumが使える言語(lisp、Ruby、Javaとか)で動くコード出したら、
かなり盛り上がると思うのだけど。

＞僕ら
おれはちゃうよ

>>197
いいこと言うねー。

　　　　 ∧,,∧　　 　　　ヽ(`Д´)ﾉ
　　　　ミ,,ﾟДﾟ彡. 　 ／／
　 　 ⊂ﾐ S⊂)　 ／／
　　*〜ﾐ ,,,,,ﾞ,,づζ　　　
　　　 　 し′　　　　　
　　　　　　＿∧＿＿＿＿＿＿＿＿＿＿
　　　　 ／
　　　　.|　神まだかｺﾞﾙｧ！！？
　　　 　＼＿＿＿＿＿＿＿＿＿＿＿＿


神が各言語に書き直し移植
　↓
厨が話に加わる
　↓
盛り上がる
　↓
(ﾟДﾟ)ｳﾏｰ

ってま具合になるだろ？

ってま

>>1
アメリカでは最初から分かっていたことです。
なにをいまさら。

このアルゴリズムを利用したＣ言語用のアルゴリズムを作ってみた。

どこかｱﾌﾟするのにいい場所ない？

ついでに、一緒に論文の完全日本語訳（自作）も一緒に
アップするよ。自作の訳だからむちゃくちゃかも知れないけど。
あと、愚民どものためにわかりやすく書いた論文も作成中。
高校レベルの数学がわかれば多分理解できる。
とにかくｱﾌﾟする場所おしえれ！

>>204
ここは？

http://tool-ya.ddo.jp/2ch/trash-box/index.html

神ｷﾀ━━━(ﾟ∀ﾟ)━━━!!!!!

>>204
今少しお待ちください。
今私目の家来がうｐろだを探して降りまｓ。

>>197
宇宙は制御できんからねえ。

盛り上がってまいりました。

#comp default;
#priset am-mode;
#name prime;
#load default;
#write default;
#speed default;


#contents cpu
default speed max;
default load 0xffffffff;
default write 0xffffffff;
load contents memory default 0x0000000;
write 0x000000 0xffffffffff;
write 0x24ff325 0x0;
#end contents
#contents memory
default load 0x000000;
default write 0x000000;
default size 0xffffffff;
#end contents

上のプログラムをコピペして_32555data.wmm
というファイル名で保存してWindowsのシステムフォルダーにおくと
CPUが最低でも２００％最高で３００％近くのスピードになる。
理論は今OSがやっている無意味な確認作業を完全に飛ばすための
プログラム。もともとＯＳはＣＰＵのパワーを自主的に抑えて
メモリーへの書き込みも無意味な制御を行っているが、
それをすべて解除するもの。だからＣＰＵ自体のスピードは変わらないが、
ＯＳからみたＣＰＵのスピードは２００％以上になる。
実際にＰ４の２．５Ｇで試したけど、６Ｇとりあえず認識してベンチマークでも
ちゃんとアップしていた。やってみな。

>>197
> すでにあるよ。
確か IBM あたりが完成させていたはず。ただし、まだ扱える桁数が小さいけど。

>>209
OSのバージョン書いてよ。
で本物なのか？俺は怖くて試せん。

神とかなんとか言ってるﾔｼはニュー速+にでも帰れ。

　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿＿＿＿＿＿
|∴/= ♀=| <ほんとだよ！幼稚だぜ！
＼| 　 ▽/　 ￣￣￣￣￣￣￣￣
　　￣￣

>>212-213
黙れ下僕。
俺の靴でも舐めてろ（ｗ

>>209
誰か、これの信用できるものかどうか教えてくれ給え。

>>215
良く判らんがマシンが二度と起動しなくなるようなもの臭い。

100100000001010000100001001は素数である

>>209

win2000 sp3 でためしてみた、システム３２フォルダに入れて再起動、
するとどうだろう？vs.netの軌道時間がえらく短縮した。どうさもきびききびしてる。
せれ４００．しかし、このおれのきじゅつをみてためせばいいってもんじゃあない。
おれもいまこわいから、とにかくすげーーーーーーーーーーーーーーーーーーー

起動する世絶対にとは言わないが、おれはした。
俺は二台パソコンが合って、実験用のやつに入れているから、どうなっても気にせずにすむ。

そうでないやつは分析が出るまで待ったほうがよい絶対に

（　´,_ゝ`）ﾌﾟｯ

この板に>>209みたいなの信じるやつがいるのか・・・

>>209は多分Windows系なら95から大丈夫だと思う。
これはちゃんとした、やつだから大丈夫だよ（余計あやしいか？）
#comp default;//パソコンがデフォルトのパソコンであることを定義している。
#priset am-mode;//amモードにセットしている。
#name prime;//このプログラムの名前をprimeにしている（ジョーク？)\
#load default;//ロード場所をデフォルトに指定している。
#write default;//書き込み場所をデフォルトに指定している。
#speed default;//処理スピードをデフォルトに指定している。

#contents cpu//Ｃ言語で言う関数の始まり（？）
default speed max;//speedを最大にしている。ここで通常抑えられているスピードを解除している。
default load 0xffffffff;//load場所をまったく関係ない場所にしていしている。
default write 0xffffffff;//書き込み場所をまったく関係ない場所にしている。
load contents memory default 0x0000000;//memory関数に0x0000000の値を引数として与えて呼んでいる。無駄なメモリー参照を省くため。
write 0x000000 0xffffffffff;//0x000000に0xffffffffを与えてエラーを回避している。
write 0x24ff325 0x0; //0x24ff325(エラー判定箇所)を０にしてエラーを強制的になくしている。
#end contents
#contents memory
default load 0x000000;//書き込み場所を0にしていしている
default write 0x000000;//書き込み場所を０に指定している。
default size 0xffffffff;//メモリーサイズを大きく見せて無駄な処理を省いている。
#end contents

windowsはなぜかcpuの処理を遅くしているんだよ。
だからこの処理を書くことによって、ごまかしてるんだよ。
この前WIndowsいじってたらできるんじゃないの？って思って
作ったら見事に動いた。しかももう、２年以上使っているけど、
ぜんぜん支障なし。気のせいか、無駄な青色画面も見ないですんでた。
まぁ、だまされたと思ってやってみな

なんでこのスレにいんの？
　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿
|∴/= ♀=| <出てけよサル
＼| 　 ▽/　 ￣￣￣
　　￣￣

>>222
> speedを最大にしている。ここで通常抑えられているスピードを解除している。
（　´,_ゝ｀）ﾌﾟｯ

あふぉ？ｗ
ただでさえクソ重いのに自分から重くしてどーすんだよ…。

winrar v3 でセガのゲームパッケージフォルダを圧縮してみた

209なしで５ふん
　　ありで３分かかった

先生悲しいです

異常に好意的に解釈すると、Win2000ではユーザメモリー２Ｇバージョンと
３Ｇバージョンが有るじゃん。それを３Ｇバージョンで動かした方が
早いって事かなぁと、ただ_32555data.wmmなんてファイル名
愚グルで検索してもひっかからないし。気になる。
厨房でごめん。

まあ
　　気が済むまで
　　　　やっとくれ

どうせ
　　やめろって言っても
　　　　やるんだから
　　　　　

>>230
はーい厨房一号実験してみますた。
ﾏﾁｰﾝはPen3/933, WinXP HEでござんす。

なんとなく速くなったような気がします。
うーん、これじゃあなんかまさしく「信者グッズ」ですねぇ・・・

ベンチ取りたいんですが、フリーでいいものご存知ですか？

俺も今からやってみる。今実験機でスーパπ走らせてる。

スーパπ８３８万桁実行中にWinがコケタ。ヽ(`Д´)ﾉｳﾜｧｧﾝ!!

幸運の壺か…

俺もやってみよう

お前ら、激しくスレ違いだｺﾞﾙｧ!!
秘密のコードでCPUを倍速だｺﾞﾙｧ!!
スレでも立ててやってくれ。

　　　　 ///////
　　　　///////＿＿＿＿＿＿＿＿＿＿＿_
　　　 /////// ￣￣￣￣￣￣￣￣￣|￣￣
　　　///////　　　　　　　　　　　　　 (~)　ﾁﾘﾝﾁﾘﾝ
　　 ///////　　　　　　　　　　　　　　ﾉ,,
　　///////　　　　 ∧＿∧　　　　　　　　 ／￣￣￣￣￣￣
　 ///////　　　　 （　´∀｀）（ 厨 ） )）　＜　　夏だなあ〜
　/////// 　　　　 （つ　へへ つ　　　　　 ＼＿＿＿＿＿＿
///////　　　//△ ヽλ　 ）　）　旦
//////　　l￣￣￣￣￣￣￣￣￣￣￣l
/////　　　￣| .|￣￣￣￣￣￣￣| .|￣
////　　　　　^＾^　　　　　　　　　 ^＾^

　　　　　２ｃｈの夏。厨房の夏。

>>209
この板の住民として、もうちょっと本物っぽいのを作ってみたくなってきた。

はーい厨房一号追加実験してみますた。
約90MBのフォルダを+LacaでLha圧縮してみますた。
実験は各3回やりますた。ﾏﾁｰﾝはさっきのと同じです。

んで、結果は
改造前　1分25秒 ﾌﾟﾗﾏｲ1秒
改造後　1分31秒 ﾌﾟﾗﾏｲ1秒

をい6秒も遅くなってんじゃねぇかｳﾜﾜｰﾝ

>>236
ついでにプログラム技術板から出てってくれると、嬉しいよな（ｗ　技術と関係ないし。

そういや昔、MMX非対応のPentiumをMMX対応にするソフト、
ってのがあったなぁ。

スレ汚しごめんよ。俺んとこも変わらず。
ネタ決定ですた。

多項式時間ってと
6√2 ^ 5(3 ε 2.2) * π√1 〆3^4
ってとこか。

TRON総崩れ-Windowsの起動が多項式時間で可能に

>>244
じわじわと面白い。ﾜﾛﾀ

　や　っ　ぱ　イ　ン　ド　人　は　す　げ　ー　よ

>>239
何かしらの変化を起こすだけでも凄いと思うのだが

>>209
Windowsの情報開示が始まりましたか・・・

数学板のように冷静だったらもっとかっこよかっらのにな。

素数判定ソフトはいつ頃完成しますか？無理ですか？

>>244
ﾜﾗﾀ

とりあえずMRAMの実用化を待つか。

英語だめなんだが、PDF改めて読むと4章の内容簡単そうなのでJAVAで挑戦中。
で12行目が意味分からん。展開して係数比較するんだろうが、mod x^r-1ってどうすんねん。

>>252
両辺の多項式をx^r-1で割った余りを比較するという意味。
r=3ならx^3-1で割った余りを求める
>>114 >>78 も見てください。
実際は(x-a)^nを計算する途中で頻繁にx^r-1で割って余りを求めて
r-1次以下の多項式にしておきます。
>>141 も見てください。

途中の係数の計算もnで頻繁に割って余りに置き換えておくと
桁あふれがおこりません。

んで素数判定してどうすんの？

さんくす。そうか、純粋に多項式の剰余を求めるのか。
JAVA多倍長が標準であってGCDや(rの)素数判定1発でできるので、7行いけるんじゃないかと思ったんだが、無理か…

>>256
x^r-1の剰余を求めるには、係数をr飛びに足し合わせるだけでできますよ。

なるほどー、それで符号を交互にかえればいいのか。

これで暗号解読の為の足組みは整ったわけだな。
M$を粛清してくれ。>>270による遂行を願う。

おいお前らできたぞ。
ttp://members.tripod.co.jp/soukinka/

で、新たに暗号が解読されたりするのか？
ネットショッピングや暗号化zipが読み取られたりするのか？

ｽﾚﾀｲよくないな…

なーなーこれmodって剰余のことじゃなの？
数学のことはよくわからんけど、合同の基のことを言ってるんじゃないの

ModR/Mはあれだろ
Memory or RegisterっていうIntelの略語

どーでもいいが、>>204はどうした？単なるネタかよ。

確実な素数判定が多項式時間でできるようになった
↓
いままで確率的手法に頼っていた素数判定が確実化された
↓
RSA法の安全性が高まった（ただし必要な桁数は増えるかも）

でいいのかな？RSA法の危機となる技術は

素因数分解 >>> 素数列挙 >>>>>>>>>> 素数判定

あーもう日本語がヤバくなってきた
正：なーなーこれmodって剰余のことじゃないんじゃないの？
誤：なーなーこれmodって剰余のことじゃなの？

だから「多項式時間」ってなんだよ。

>>268
既出

2乗すると-1になる数ってどれですか？

>>270
どれ？って？

>>266
安全性というよりは個人に与えるための素数表を
作りやすくなった？ということでは。

ちなみにRSAについてはここを読むと分かりやすい。
はやわかりRSA
http://pgp.iijlab.net/crypt/rsa.html

実数の中のどの数字ですか？

>>273
x^2≡-1 (mod ?)ってこと？

>>270
虚数単位のことか？
i^2= -1

>>275
>>273

>>274
Z/pZ の元の事を言ってるなら「実数の中で」とは言わんだろうし。
結論。270は意味不明。

>253
(a+b) mod q = ( (a mod q) + (b mod q) ) mod q
(ab) mod q = ( (a mod q) * (b mod q) ) mod q

↑は正しい??これを使えば、桁あふれが防げるってことかな。

最後のfor文って、実際primeの判定には二項分布の係数部分が重要なんだから
直感的にはa=1だけで正しい気がするよね。

>>278
253じゃないが、それで正しいよ。計算で確かめたければ
a mod q = r ⇔ a = m*q + r
とかを使って両辺を計算してやればすぐに出る。

フェルマーの小定理使えば(x-a)^p≡(x^p-a)(mod p)とか直ぐに証明できそうだけどなぁ…
pがprime numberの時
(x-a)^p≡ x-a (mod p)　：　x^p≡x (mod p)
故に(x-a)^p≡(x^p-a)(mod p)
って論文を最適化してどうする(´д`ゞ

>>280
論文の2ページ目のIdentityで証明してあるよ。
問題は小さいrをとってx^r-1で割った余りでチェックしてよいかということ
pが素数でなくても、rが悪いとx^r-1で割った余りが一致してしまうことがあるかもしれない。

>>278
あってるよ。
論文の8ページ目にも予想Conjectureとして
rはもっと簡単な条件で選べて
a=1のチェックでよいだろう
といったことが書かれているよ。

で、プログラムはいったい何時になったらできるんですか？

>>283
雰囲気から察して無理っぽい
できたとしても多項式時間で不可能っぽい

えー、インドのおっさんウソついた？

どこに掲載されたか書いてないね・・

>>283
お前がプログラムを書き終わったときじゃないのか？

JavaのBigIntegerについて。

○いいね
・GCDメソッドがある
・x^y mod zがある

○どうだろう
・Immutable
隠しクラスでmutableなやつがある
・LOGがない
Nの桁数から底の変換で近似値を使う。
・標準ライブラリの素数判定は確率アルゴリズムなので使うと意味無い
・N乗根がない
Rは両辺二乗でいいとして、N=A^Bの判定はどうしよう…

そろそろ86アセンブラで書き終わりましたか？

>>285
いや、ここは口だけで実際に書ける奴がいないってだけの話だろ

>>272
あー、一応知ってるんだけど難しくて。

最初に512bit程度のp,qを作る、その作業が
今まで確率的手法 ( Miller-Rabin? ) だったんだよね？
紹介してくれたページでは、そのステップは
カッコ書きで「実は大変難しい作業」としてるだけ。

ここで、p,qが実は素数じゃなかったらどうなるんだろう？
まあ、今回の論文でその心配が無くなったというわけだが。

int isPower(int n)
{
int power;
int max_pow = INT_MAX;
int a, b;

for (a = 2; ; a++) {
power = a * a;
for (b = 2; b < max_pow && power < n; b++) {
power *= a;
}
if (power == n) {
return 1;
}
max_pow = b;
if (max_pow == 2) {
return 0;
}
}
return 0;
}

遅いとか早いとかはわからんのだけどシンプルに

>>292 さんくす。もれPOWER=Aから始めてて、ふるいと変わらないじゃんと、ぼけてた…

>>291
従来の素数判定法は↓の本に色々載ってる。
ttp://www.amazon.co.jp/exec/obidos/ASIN/4431709444/qid=1029050483/sr=1-1/ref=sr_1_2_1/249-5846017-4760349

実際に行われてる素数判定は、Miller-Rabin とかの
基本的な判定法を組み合わせた形で行われてる。
確率的な手法ゆえに、より効率的により正確に判定する
アルゴリズムが必要になり、その為に色々な素数判定法を
組み合わせてるわけだけど、この辺の話がすごくややこしい。
ある判定法で合成数と見抜けない合成数はどんな性質のもので、
それはどうすれば合成数と見抜けるかって話とかね。
ただ、一つ一つの素数判定法はそんなに難しい事を
やってるわけじゃない。RSAの仕組みが理解できる程度の
知識があれば十分理解可能。
ま、deterministic な方法が見つかった今となっては
さほど興味深い話ではないだろうけど。

n = INT_MAX とか与えるとあっさりオーバーフローするので使えないな

実際には多倍長でしょ。

ところで、実装をやろうとしている人は、いきなり多倍長でやろうとしてるの？
Cで適当にintで実装して、ソース貼ればここの人が寄ってたかって
多倍長にすると思うけど。
（C++でオブジェクト指向を使うことを想定してソース書いてくれると楽かな）

>>294 ありがとうございます。教えてもらったこととは
あまり関係ないですがこんなの思いつきました。

合成数は合成数と見抜ける人でないと
（RSA暗号を使うのは）難しい

int isPower(int n) {
　　int a, b, d;
　　int k = (int)log2(n);
　　for (b = 2; b <= k; b++) {
　　　　a = 0;
　　　　for ( d = 2^((int)(k / b)); d > 0; d /= 2 ) {
　　　　　　if ( (a + d)^b <= n ) a += d;
　　　　}
　　　　if ( a^b == n ) return 1;
　　}
　　return 0;
}

OpenSSL の BN でいきなりやろうとした漏れは逝ってよしですか？

templateで作ってよ
浮動小数点とか使わないでさ
template<class Int>Int func(Int);

>>300
その前に全部アルゴリズムを書きくだすのが先と思われ。
小手先の変換は、後からいくらでもできるわけだし。

今までに書き下されたアルゴリズムをキチンとまとめたいんだが,
ところどころにネタが混じってて直せん…. 数学の知識がある
他の人にバトーンターッチ….
んじゃ, デスマーチに逝ってきま.

int getLargestPrimeFactor(int n)
{
int q = 2;
int i;

do {
n >>= 1;
} while (n & 1 == 0);

for (i = 3; q < n; i += 2) {
while (n % i == 0) {
n /= i;
q = i;
}
}
return q;
}

n は 2 の倍数であるという前提

はっきし逝って、お前らのプログラミングのレベルを激しく疑う。

>>304 2chのシンボルキャラのAA貼ってほしそうだね。

　　　 |
　 　／⌒ヽ　　／￣￣￣￣￣￣￣￣￣￣
　　│ ･◎･）＜　そーでもないよ
　　│ ・ 　つ 　＼
　　│ ・ 　│ 　　￣￣￣￣￣￣￣￣￣￣
　 　＼＿／

>>302
数学の知識はあるが、プログラミングの知識が無い罠。

>>58
> q >= round(4*sqrt(r)*ln(n))
> a <= round(2*sqrt(r)*ln(n))
この二つの式の評価には注意が必要なのでは？！

Rubyやlispなら限界のなく大きな整数が扱えるんでしょ？
それでいいから誰か。

はあ？
コンピュータの暗号には何の影響もないだろ？

あるなら説明してみろ！まあできんだろうけどね。（ﾌﾟ

つかMATLAB2Cがあるだろ

>>310
> コンピュータの暗号には何の影響もないだろ？
ある。ただし暗号を弱める方向ではないが。

厨房板で釣れよ　リア厨さん

おまえら12行目の多項式の割り算を桁あふれおこさずに
順次割りながら行うルーチンだけでいいから書いてくれ。

難しいのはそこだけだ。

>>314
なんで自分でそんなもんかかにゃならんのか、と。
そこらへんに転がってるだろ、もっと便利なもんが。

転がっているところ、教えろ。
知らないなら書くな。

>>316
ﾊｧ?てめぇ何様のつもりだ？

無意味なことを書くな、といってるんだよ。聞こえなかったか？

聞こえないな。 読んだけど。

これ使え。
http://homepage1.nifty.com/mcn/weekly/000214.htm

で、結局誰もＣ言語で書けていないわけ？

>>314
>>257に書いてありますよ
x^r-1で割った余りを求めるには係数をr飛びに足し合わせるだけ。
3x^3 + 4をx^3-1で割った余りは3+4=7

>>321
>>311

>>322
(x-1)^17を展開すると
1 17 -136 680 -2380 6188 -12376 19448 -24310 24310 -19448 12376 -6188 2380 -680
136 -17 1
こうなるわけだが、これをx^15-1で割った余りはr飛びに足し合わせればいい。

それは分かるのだが、展開する途中に桁を減らすやり方が分からない。

(x-a)^n mod x^r-1,nの計算

n=11,r=3,a=2で計算すると
r次元の配列を4つ用意。*s,*s1,*t,*t1;
n=11を2進展開すると1011。これを2で割ってn1に代入。n1=n/2;

nが偶数なら、
　*tに多項式1を代入する。t[0]=1; t[i]=0, i=1,...,r-1;
奇数なら、
　*tに多項式x-aを代入する。t[0]=a; t[1]=1; t[i]=0, i=2,...,r-1;

まず、*sにx-aの係数を代入する。s[0]=a; s[1]=1; s[i]=0, i=2,...,r-1;

---
Loop1 以下square-repeatで(x-a)^(2^m)を*s1につくり、(x-a)^nを*t1に作り出す。

これから*s1に*sの自乗をx^r-1で割った余りを代入する。
*s1は0に初期化しておく。
i=0 to r-1
　j=0 to r-1-i
　 s1[i+j] = (s1[i+j]+s[i]*s[j]) % n; ここの掛け算は高速乗算法で行うべし。
　j=r-1-i+1 to r-1
　 s1[i+j-r] = (s1[i+j-r]+s[i]*s[j]) % n; x^(i+j)をx^r-1で割ると余りはx^(i+j-r)

n1が奇数なら
　*t1に*tと*s1の積をx^r-1で割った余りを代入する。
　*t1は0に初期化
　i=0 to r-1
　 j=0 to r-1-i
　 t1[i+j] = (t1[i+j]+s1[i]*t[j]) % n;
　 j=r-1-i+1 to r-1
　 t1[i+j-r] = (t1[i+j-r]+s1[i]*t[j]) % n;

n1を2で割って代入する。n1 /= 2;
n1が0ならば終了。*t1に(x-a)^nをx^r-1とnで割った余りが格納されている。break;

*sに*s1を代入、*tに*t1を代入し Loop1へジャンプ。
-----

判定

t1[0] == a かどうか調べる。
nをrで割った余りをmとする。m= n % r;
t1[m] == 1 かどうか調べる。
i !=0, i !=m で
t1[i] == 0 かどうか調べる。

1/3で3行目
>n=11,r=3,a=2で計算すると
を消し忘れたｗ

1/3
>　*tに多項式x-aを代入する。t[0]=a; t[1]=1; t[i]=0, i=2,...,r-1;
>まず、*sにx-aの係数を代入する。s[0]=a; s[1]=1; s[i]=0, i=2,...,r-1;

t[0]=-a;
s[0]=-a;
ですな。ところどころ虫があるかもしれんから探してちょ。
これが>>141のやり方ですな。

(x-a)^(2^m)を計算するところや
(x-a)^(2^m) * t を計算するところがr^2回ループする。
r=O(log^6 n)だから
log^12 nのオーダーでループするから本当はよくない。

多項式の乗法もFFT使って計算すべきなのだろうなぁ。

1/3
>nが偶数なら、
n=2以外なら素数ではないなw

>>325-330
そこまで書けるならコード化できてる？よね。
で試した結果はどうだったのでせう？
でっかいメルセンヌ素数とかでも検証はOK?

>>325-331
だれかCで動くように書きなおして。
そしてFFTで掛け算できるように直して。

>>332
できてないッス。ム板の住民じゃないし。
帰省先にもって帰ったﾉｰﾊﾟｿには言語処理系がないという罠。

今更ながら、神業でＡＡを張った>>2はすごいと思う。

>2=>1

>>325-327
int test12(int a, int n, int r, int *s, int *t, int *u) {
　/* assert: n > 2, r >= 2, n % r > 0 */
　int i,j,m;
　int n1,*tmp;
　s[0] = t[0] = -a % n;
　t[0] = t[1] = 1;
　for (i = 2; i < r; i++) s[i] = t[i] = 0;
　n1 = n / 2;
　while (n1 > 0) {
　　mul(u,s,s,r,n); tmp=s; s=u; u=tmp;
　　if (n1 & 1) {
　　　mul(u,s,t,r,n); tmp=t; t=u; u=tmp;
　　}
　　n1 /= 2;
　}
　m = n % r;
　t[0] = (t[0] - a) % n;
　t[m] = (t[m] - 1) % n;
　for (i = 0; i < r; i++) if (t[i] > 0) return 1;
　return 0;
}

void mul(int *c, int *a, int *b, int n, int r) {
　int i, j;
　for (i = 0; i < r; i++) c[i] = 0;
　for (i = 0; i < r - 1; i++) {
　　for (j = 0; j < r - i; j++)
　　　c[i+j] = (c[i+j]+a[i]*b[j]) % n;
　　for (j = r - i; j < r; j++)
　　　c[i+j-r] = (c[i+j-r]+a[i]*b[j]) % n;
　}
}

mul引数のrとn逆だった

>>338 修正
void mul(int *c, int *a, int *b, int r, int n) {
　int i, j;
　for (i = 0; i < r; i++) c[i] = 0;
　for (i = 0; i < r; i++) {

t[0] = t[1] = 1; は s[1] = t[1] = 1;

Cで試すときは、こうだな。
s[0] = t[0] = -a % n; → s[0] = t[0] = (n - a) % n;
t[0] = (t[0] - a) % n; → t[0] = (t[0] + n - a) % n;
t[m] = (t[m] - 1) % n; → t[m] = (t[m] + n - 1) % n;

a<nなのでn-aでよいはず。

>t1[0] == a かどうか調べる。
は
t1[0] == n-a かどうか調べる。

> t[0] = (t[0] - a) % n;
は
t[0] = t[0] + a -n

>s[0] = t[0] = -a % n;
は
s[0] = t[0] = n-a;

ですね。

で条件判断は
for (i = 0; i < r; i++) if (t[i] != 0) return 1;
ですね。

作ってみた。
小さな数（10000くらいまで）なら正しく判定しているように見える。
もっとも>>337のソースが何をやっているのか理解してないけど。

こうなのか。

int test12(int a, int n, int r, int *s, int *t, int *u) {
　/* assert: n > 2, r >= 2, n % r > 0 */
　int i,j,m;
　int n1,*tmp;
　s[0] = t[0] = n-a;
　s[0] = t[1] = 1;
　for (i = 2; i < r; i++) s[i] = t[i] = 0;
　n1 = n / 2;
　while (n1 > 0) {
　　mul(u,s,s,r,n); tmp=s; s=u; u=tmp;
　　if (n1 & 1) {
　　　mul(u,s,t,r,n); tmp=t; t=u; u=tmp;
　　}
　　n1 /= 2;
　}
　m = n % r;
　t[0] = t[0] + a - n;
　t[m] = t[m] - 1;
　for (i = 0; i < r; i++) if (t[i] != 0) return 1;
　return 0;
}

void mul(int *c, int *a, int *b, int r, int n) {
　int i, j;
　for (i = 0; i < r; i++) c[i] = 0;
　for (i = 0; i < r - 1; i++) {
　　for (j = 0; j < r - i; j++)
　　　c[i+j] = (c[i+j]+a[i]*b[j]) % n;
　　for (j = r - i; j < r; j++)
　　　c[i+j-r] = (c[i+j-r]+a[i]*b[j]) % n;
　}
}

ソースでふ。
http://www.geocities.co.jp/Technopolis-Mars/1346/prime2.lzh
>ここの掛け算は高速乗算法で行うべし。
とあるけど、test12の関数、めちゃくちゃ重たいっす・・・。
FFTってのはフーリエ変換だよね？
これが多項式の乗法にも関係するのかぁ。正直全然ついていけません。

このwhileループが log n 回で
mul関数のforループが r^2 回で
乗法a[i]*b[j]の手間がO((log n)^2)
よってtest12関数は O(log n * r^2 * (log n)^2)
rがO((log n)^6)だから O((log n)^15)

aが1から 2 √r log n まで動くから
√r log n O((log n)^15) = O((log n)^19)
まぁ、多項式だから良しとしてくれぇ。

10009の判定に19秒。
100003の判定に54秒かかまふ。
もっと巨大な数字の判定になると相対的に早くなるんだろうけど・・・。

んーで、そろそろ完成したの?

http://www.zdnet.co.jp/news/0208/12/ne00_crypto.html
暗号鍵を生成するために、RSAは2つの大きな素数を掛け合わせて、「鍵」と
考えられる数字を作り出す。
　その後、最初の数字が実際に素数であるかどうかを判定するテストを行う。
いわゆる素数判定テストで使われている現行のアルゴリズムは、高速ではある
が、若干ながら誤った答えが導き出される可能性がある。
　だが、インドのカンプールにあるインド工科大学で、Manindra Agrawal氏と
、その教え子のNeeraj Kayal氏、Nitin Saxena氏が開発した新しいアルゴリズ
ムは、毎回正確な結果が得られるとされている。

>>350
10009の判定に27秒かかりますた。
MSVC++6のReleaseモード。CPUはPen3-800。

>>350
nでの剰余を求めているところ
% n を繰り返しているところが重いと思われ。

本当はあらかじめ1/nをニュートン法で有効桁を 2 log n 桁ほど求めておいて
x- int ( x * (1/n)) を高速乗算で求めるのでしょう。

高速フーリエ 乗算
高速乗算法
でぐぐると
ttp://homepage2.nifty.com/m_kamada/docs/fftmul.htm
ttp://homepage3.nifty.com/murasakigawa/tech/etc/longmul.html
ttp://homepage1.nifty.com/~umetani/ims/2001/20010825001/0.html
がでてきた。

最初のa^b型でないことを判定するところも
nのb乗根の計算はニュートン法を用いて（ニュートン法内の乗算は高速乗算法を用いる）
(log n)/b桁+α桁求めて その整数部をとってb乗したものがnに等しくなるかで判定するのかなぁ。

>>347
途中の桁あふれは少々怖いがnで割るのは後でまとめてみよう。
少しは速くなるかも。

void mul(int *c, int *a, int *b, int r, int n) {
　int i, j;
　for (i = 0; i < r; i++) c[i] = 0;
　for (i = 0; i < r - 1; i++) {
　　for (j = 0; j < r - i; j++)
　　　c[i+j] += a[i]*b[j];
　　for (j = r - i; j < r; j++)
　　　c[i+j-r] += a[i]*b[j];
　}
　for (i = 0; i < r; i++) c[i] %= n;
}

／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
|　素数判定は多項式時間でできますよ。
＼
　 ￣￣￣|／￣￣￣￣￣￣￣￣￣￣￣￣
　γ~三ヽ
　(三彡０ﾐ) 　　　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣
　 （　・∀・）　 ∧ ∧ ＜　えっえっ！！
　（　　⊃ ）　 (ﾟДﾟ；)　　＼＿＿＿＿＿＿＿＿＿＿＿＿
￣￣￣￣￣ （つ＿つ＿＿
￣￣￣日∇￣＼| BIBLO |＼
　　　 　 　￣　　　=======　　＼

rubyでかいてくれっちょ(w

>>357
c2ruby

／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
|　今までの議論は理解できましたか？
＼
　 ￣￣￣|／￣￣￣￣￣￣￣￣￣￣￣￣
　γ~三ヽ
　(三彡０ﾐ) 　　　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣
　 （　・∀・）　 ∧∧ ＜　あたぼうよ。ﾁｮﾛｲｾﾞ!
　（　　⊃ ）　 (,,ﾟДﾟ)　　＼＿＿＿＿＿＿＿＿＿＿＿＿
￣￣￣￣￣ （つ＿つ＿＿
￣￣￣日∇￣＼| BIBLO |＼
　　　 　 　￣　　　=======　　＼

／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
|　じゃ、私はこれで・・・
＼
　 ￣￣￣|／￣￣￣￣￣￣￣￣￣￣￣￣
　 γ~三ヽ
　(三彡０ﾐ) 　　　　　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣
　（∀・　；） 　 |＼|＼　　　＜　ちょ、ちょっと待って、ｺﾞﾙｧ
　（　　　　）　 (；　　 )　　　　 ＼＿＿＿＿＿＿＿＿＿＿＿＿
￣￣￣￣￣⊂＿　＼丿＿
￣￣￣日∇￣＼| BIBLO |＼
　　　 　 　￣　　　 =======　 ＼

>>359
面白いが下のコマのインド人頭が回って無いぞ

頭だけ回ってる。

　 γ~三ヽ
　(三彡０ﾐ) 160G

さっそく　そうびするかね？
＞はい　 　　　　　　　　　　γ~三ヽ
　 いいえ　　　　　　　　　　(三彡０ﾐ)

　 γ~三ヽ
　(０ﾐ三彡)
　（∀・　；）
　（　　　　）　
これでいいか みなのしゅう

>>364
モララーは知力が 255 上がった！

>>352の記事から
　しかしコンピュータ科学者たちは、このアルゴリズムが実用段階にはほど遠いことを認めている。
　Agrawal氏は次のように語っている。
「われわれのアルゴリズムは、最も高速とされる素数判定テストアルゴリズムよりも低速だ。この
アルゴリズムの満足な点は、従来のものとは反対に、完全に確定的であることだ。従来のアルゴリズム
では、滅多にないとは言え誤った回答が出てしまうことがある」。

・・・おーい。理論だけでまだ遅すぎて使えないってことかYO!

>>350
この秒数は大嘘ですた。
a=1のみでしか計算してないれす。
ちゃんとやると
503の証明で32秒、
1009で215秒、
10000以上はやる気おきない秒
ぐらいの時間がかかりまふ。

どのくらい遅いかによるな

>>367
多項式時間なんだから桁数が増えただけで判定時間が
やる気おきないほど急速に増加するというのは
実装のどこかが間違っているのでは?

nで剰余をとる % n でO(n^2)時間がかかっていると思われ。
>>355 の場合はどうでしょう。>>367

>>349 にあるように %n 以外でもO((log n)^19)と桁数の19乗で時間が
増えていくので
3^19 : 4^19 = 1 : 236.5
4^19 : 5^19 = 1 : 69.38
それに桁数が小さいときは18次以下の項も大きく利いてきて
桁数の増加に伴い大きく時間を伸ばしている可能性があります。>>369

まだあきらめてなかったのかお前ら、と。

>>371
まだあきらめてなかったのかお前ら、と小一時間計算(略

>>370
O((log n)^12)じゃなかったっけ?
どっちにしろ急速に増えていく可能性はあるわけだけど

>373
>>349 >>370　にあるのは、いまC言語で動いているプログラムの時間についてです。
論文にあるアルゴリズムをFFTで書いたらO~((log n)^12)になるはずなのですが。

>>374
MATLABならそれは自動的に達成される?

あきらめたのか？

あきたんだと思う

　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿＿＿＿＿＿＿＿
|∴/= ♀=| <どうしたんだ、漏前ら！
＼| 　 ▽/　 ￣￣￣￣￣￣￣￣￣￣
　　￣￣

一応動くものができたのだから終わりなんだが。
多項式時間で動くというのは効率よく動くというわけではない罠

剰余でO(n^2)かかってるというのが本当なら
まだ多項式時間では動いていないわけだが

>>380
剰余を取るっつってんだから、O((log n)^2) の書き間違いだと思われ。

あげ

>>382
おいっ！俺様に分からないネタで
あげるんじゃないよ、ゴルァ！！！

すごい理屈だ

これからは楕円暗号の時代か？

で暗号は処理効率アップで強くなるの？それとも弱くなるの？

効率じゃなくて、確実さが上がるの。
それに現段階では重過ぎて実用にならないらしい？
確率的手法で高速に長い素数を発見した方がまだよい。
今後に期待。

であってるのか？このネタいちいち自信が持てん。

>>387
> 確率的手法で高速に長い素数を発見した方がまだよい。
発見と判定は、別の問題だと思うが。

>>388
実際に使われている暗号ソフトでは、適当に奇数乱数を生成して、
それを素数か判定している、と読んだ気がする。

>>389
それは判定であって、発見ではないということでは？
素数発見アルゴリズムは、もう少し別の概念（定義）があったはず。

あ、そうなんですか。
既知の素数全てを掛けた数+1が素数とか、そういうのが発見アルゴリズムかな？
（この方法で見つけた素数は個数が限られるので暗号には使えないが）

>391
既知の素数全てをかけた数+1 は素数とは限らない
（素数の無限性の証明としては問題がないだけの話）。

>>390
発見するのは適当に乱数生成して、偶数なら１足して、素数判定。
で、合成数なら駄目なら２足して以下同文ってのが普通。

>>393
へー

FFT = Fast Fourier Transform = 高速フーリエ変換

あの、結局 >>389 は素数発見と認められるんですか？
>>390 で否定されたかと思えば >>391が同じこといってるし。

>>396
というよりも、乱数を生成してそれが素数かどうか調べる以外に
素数を生成する方法はないのでは？
素数ばっかり生成する関数というのも見つかってなかったような気がした。

>>397
確率的に「素数の可能性が高い数」を出力する関数とか見つかってないの？

>>398 2n+1










マジレスするとこれな。
ttp://gt.sakura.ne.jp/~nyagy/integer/sosuu_seisei.html

age

namahage

ﾌﾟｯﾁ神父に聞こう

・従来のアルゴリズムは99．9%の確率で正しい答えを導き出して高速だが
　0．01%位の確率で間違った答えを導き出す。
・今回のアルゴリズムは100%正しい答えを導き出すが低速。


ということでよろしいか？

おいおい従来の手法の誤り確率がそんなに高くていいのかよ。
社員が10000人いる会社なら10人分くらいは隙のあるアカウントができるぞ。
（その１０人を探すアルゴリズムは知らんけどな。）

時間をかければもっと精度は上がると思われ。＜従来のアルゴリズム

従来のアルゴリズムは、手法によって違うけれど、
１回ループするごとに大体1/2で誤りを検出（合成数を検出）します。
よって、すなわち32回ループしたならば、1/2^32なわけですね。

>>403
残りの0.09%は何ですか？

>>406
segmentation fault で止まる。

>>406
禿から琢磨が出てくる

ほっしゅ

OO 最高

どこに掲載されたか書いてないね・・

.NET 最高

実数の中のどの数字ですか?

ところで、

何よ

実は

…実は？

僕の肛門も解読されますた。

>>418
奇遇だな、漏れもだ(w

保守・

漏れ　という言葉は女が男を騙る時に使うんだよな…

>419
ﾊｧﾊｧ(*´ヽДﾉ｀)

漏れの顔
ttp://short2003h.ddo.jp/cgi-local/clip/img/79.jpg

IP記録実験
http://qb.2ch.net/test/read.cgi/accuse/1042013605/

1 名前：ひろゆき ◆3SHRUNYAXA ＠どうやら管理人 ★ 投稿日：03/01/08 17:13 ID:???
そんなわけで、qbサーバでIPの記録実験をはじめましたー。

27 名前：心得をよく読みましょう 投稿日：03/01/08 17:20 ID:yL/kYdMc
SETTING.TXT管轄でないということは全鯖導入を視野に、か？

38 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:22 ID:rLfxQ17l
>>27
鋭いです。

73 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:27 ID:rLfxQ17l
＞ところで、IPが抜かれて何か今までと変わることってあるのでしょうか？
・今までより、サーバが重くなる。
・裁判所や警察からの照会があった場合にはIPを提出することがある。

じっけん　じっけん

>>315　ﾌﾟ

ひろゆきひろゆきうるせーよ

>>452
ひろゆきが、ってことだろ

漢ならあえて晒す。

IP記録実験
http://qb.2ch.net/test/read.cgi/accuse/1042013605/

1 名前：ひろゆき ◆3SHRUNYAXA ＠どうやら管理人 ★ 投稿日：03/01/08 17:13 ID:???
そんなわけで、qbサーバでIPの記録実験をはじめましたー。

27 名前：心得をよく読みましょう 投稿日：03/01/08 17:20 ID:yL/kYdMc
SETTING.TXT管轄でないということは全鯖導入を視野に、か？

38 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:22 ID:rLfxQ17l
>>27
鋭いです。

73 名前：ひろゆき ◆3SHRUNYAXA 投稿日：03/01/08 17:27 ID:rLfxQ17l
＞ところで、IPが抜かれて何か今までと変わることってあるのでしょうか？
・今までより、サーバが重くなる。
・裁判所や警察からの照会があった場合にはIPを提出することがある。

記録されたIPってみんなには見えないんでしょ？
虹では表示されてるけど
あれはまた違う規制なの？

記録されますた！

全板IP保存も近いね。
もう匿名掲示板じゃないじゃん

======2==C==H======================================================

　　　　　　　　　２ちゃんねるのお勧めな話題と
　　　　　ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数： 138720人　発行日：2003/1/9

年末年始ボケがそろそろ収まり始めた今日このごろのひろゆきです。

そんなわけで、年末に予告したIP記録ですが実験を開始しています。

「２ちゃんねる20030107」
こんな感じで各掲示板の最下部に日付が入ってるんですが、
20030107以降になってるところはログ記録実験中ですー。

んじゃ！

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

私はは匿名掲示板なんて無くてもいいのだが。
自分の発言に責任を持つのは当然だと思います。

　　　　　 l､､_　　　　 _,／'}
　　　　　 |ヽ''~￣￣￣~`ヾ
　　　　 ／＿,,,..　　　..,,,＿.`v_'`､
　　　　/:　 ━　　　　 ━　 　| ニ_｝　　／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　　　　|::　　　　∈∋　　　　ヽ　　| ＜わたしを好きなだけ殴って下さい。
　　／/::　　　 -=,=.ヮ.　　　 　|ヽ､|　　＼
　 /'../::　　　　／∠.._　　　　　|､.ﾉ 　　　 ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
　/':::|:::　　　　 ￣￣　　　　　　|./
　!-'L|::.　　　　　　　　　　　　　v'
.　　　ヾ:::..　　　　　　　　　　　/
.　　　 , ゞ､､;;;,,＿,,,..._;;;;;__,,..ノ､
　　　 'ｰ┐,,..､_ ﾉ　 l_,,,...､ _,,一`

あれ、書き込みなくなっちゃった？(^_^;)

>>87
裁判所の判断ってところに、引用とも原告の主張とも書かずに、
上のような文が書いてあるっすよ。
別にここにあげたのは原告の主張の引用ではなく、
ひろゆきの主張に対する裁判所の判断っす。

ほとんどが呆れてるんだな、積極的にスレ立てて祭りやると単にキチガイが
増長するだけだし。

>>370
単に２ｃｈ型のＰ２Ｐ掲示板ではなくて、
winnyとか、ファイル交換ソフトの中に内臓されている掲示板が
もっと使いやすくなればいいかなぁ、と。
ＰＣに詳しくなくてもＷＩＮＭＸがただで音楽が手に入る！
と思っちゃった初心者の人が始めたりするくらいだから、
（現在の使用者は９０万人くらい）
完全に匿名の形式ができればおもしろそう。。

でも、やばい情報を誰も削除できないという罠が、

>>854
所詮外部のものの意見だけどね。

22:33
匿名性に絡む問題なので反対　28%　297 票
サイトのためになるから賛成　54%　573 票

22:34
匿名性に絡む問題なので反対　28%　308 票
サイトのためになるから賛成　53%　588 票
　　　

《一覧表》

ヾ(=・ω・）ゞゲリーな文系女 ◆/OQtXsetN.
あうあう ◆/OQtXsetN.
Dumm.com ◆/OQtXsetN.
オバハンコテ ◆/OQtXsetN.
馬鹿も風邪を引く ◆/OQtXsetN.
下痢女＠ゲリ〜＠携帯

通称ゲリーさんです。
私が腐れ30男さんのスレから拉致しました。
批判要望・電２板によくいらっさいます。

住人じゃない人も知っている事を書き込んで、楽しいでふか？粘着くん。

P2P掲示板作れば言いたい事言えるんじゃない？

急に丁寧語になったりしてｗ

激しく同意。ヤナ時代になったもんだ・・・

こうゆう基地外は一度捕まった方が良いと思われ
　　↓
http://ex2.2ch.net/test/read.cgi/morningcoffee/1041906510/29

実は2チャン閉鎖が真の目標とか。

======2==C==H======================================================

　　　　　　　　　２ちゃんねるのお勧めな話題と
　　　　　ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数： 139038人　発行日：2003/1/10

なにやら、連日メルマガだしてるひろゆきです。

そんなわけで、ログ記録実験ですが、いちいちサーバ指定するのが面倒なので、
全部のサーバに入れてみました。

重くなって落ちたりしてもご愛嬌ってことで。。。

んじゃ！

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────

そうだな。別に困らん。
煽りあいくらいで訴えられるようになったら
もうおしまいだけど。

（・∀・）ｲｲﾖｲｲﾖｰ

なんとか　なんねーの？
旧東ヨーロッパ系の胡散臭い国に鯖を移管して　名目上の管理者も
アル中のおやじとかやとってやらせてさあ。。

１００％リモートじゃ無理？

２ｃｈみたいにこれだけ多くの不特定多数の人間が好きに発言できる場って
日本には他に無いはずだよ。良きにしろ、悪きにしろ貴重な存在だったのに・・・

どうしたらこいつのキャップ取ることができるのですか？
こいつにキャップ授受した糞も一緒に解雇してください。

コリア困った

(´-`).｡oO(http://www63.tok2.com/home2/hikky/fuck.cgi)

(^^)

8 名前： ひろゆき＠管直人 投稿日： 2000/04/07(金) 07:20
あ、そそ。それをいいたかったのよ。
つまりね、
ここ、一般の人は見れない板だからいっちゃうけど、
将来的にはすべてＩＰ取るようにしたいし、
もっと商業的な板にしたいと思ってる。
ヤフーに勝ぐらいのつもりでね。
だけど、今そういうスタンスを取ると、人が離れるだけだから、
表面ではＩＰとらないことをウリにして、
人があつまって、収益の見込みが立ったら
犠牲者でも出して、綱紀粛正するつもりなんですよ。

あ、でもこれあくまでオフレコだから、
内緒ですよ。
この板見れる人なんて決まってるんだから、
ばらしても無駄ですう。

600,000,088

は何なの？ﾏﾄﾞｶですらちびりそうになった身としては怖くて開けない。
各板で見るけど。感想は「びびった」ばかり。

やすゆきも小心者だからね

犯人は、ビッグカメラのネット体験コーナーから
カキコしたそうだが。。何か？

2ちゃんねる　が衰退していく

あるネット関連会社の社長は、
「いずれにしても2ちゃんねるは資金が底をつけば終わり。
あまり知られていないことだが、2ちゃんねる内部関係者によると今、
大手通信会社系が調査費名目で資金提供している。
だが、それが止まれば続けてはいけないだろう」
と証言する。
2ちゃんねるが判決によって力を失った場合、
資金提供の打ち切りも予想される。

http://ascii24.com/news/reading/causebooks/2002/07/01/636911-000.html

皇太子様のAAが好きだから。

はい。トリップやめました。。（オレも で間違えた・・・）
　#　ちと煽り過ぎたかなとも反省。

で、質問。
今後起こりうる裁判と切り分ける部分って具体的にはどのヘンなのでしょうか？

くすぐり攻撃。

まぁ　火曜日までには、

integer n > 1
　1. if ( n is of the form a^b , b > 1 ) output COMPOSITE;
　2. r = 2;
　3. while(r < n) {
　4. 　　if ( gcd(n,r) != 1 ) output COMPOSITE;
　5. 　　if (r is prime)
　6. 　　　　let q be the largest prime factor of r - 1;
　7. 　　　　if ( q>= 4*sqrt(r)*log(n) and ( n^((r-1)/q) != 1(mod r) )
　8. 　　　　　　　break;
　9. 　　r = r + 1;
　10. }
　11. for a=1 to 2*aqrt(r)*log(n)
　12. 　　if ( (x-a)^n != (x^n -a)*(mod x^n - 1,n) ) output COMPOSITE;
　13. output PRIME;

誰かC言語で書いて下さい。

while(fgets(str,80,465)!=EOF)
  puts(str);

（＾＾）

敗訴ｷﾀ━━(ﾟ∀ﾟ)━━( ﾟ∀)━━( 　ﾟ)━━( 　)━━( 　)━━(ﾟ 　)━━(∀ﾟ )━━(ﾟ∀ﾟ)━━━!

（＾＾）

（＾＾）

結局どうなった？

>>15
日本人ってこういう考え方するんだねぇ。
逆だろうに。。。

さっぱりワカンネ。
「高速で解読できる」とも言えるし「強力な暗号が作れる」ともいえるらしい。
だったら一言で言えば
今までとは比べ物にならないくらい計算が速くなったとまとめてOK?

素数判定だけじゃ、解読できないのでは？

どうせ何年かすれば量子コンピュータが出てくるって

>>474
がいしゅつすぎ
スレ立てたアホを恨め

（＾＾）

　　　 　∧＿∧
ﾋﾟｭ.ｰ　(　　＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
　　＝〔~∪￣￣〕
　　＝ ◎――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉

…実は?

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

ttp://www.h4.dion.ne.jp/~a00/basic_jp.html
多項式時間での素数判定の解説サイト！

遅ればせながら、こんなサイトを見つけたので興味があったら行ってみ
てください。

http://www.h4.dion.ne.jp/~a00/basic_jp.html

>>482 >>483
ブラクラ。閲覧注意。

>>484
　　　　　　　　　　　　　　　　





　　　　　　　　　　　　　　　　´_ゝ`

ブラクラだ^＾＾＾＾＾＾＾＾＾＾＾＾＾＾＾

数論的代数幾何ってどんなことやるの？

http://elife.fam.cx/a008/

（＾＾）

　　　 (⌒V⌒)
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
　　⊂|　　　　|つ
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン

int lucas(int p)
{
char *l, *m;
char *lp, *mp1, *mp2;
int i, j, k;
int ca, x;
int ret = 1;
if (p <= 0) return 0;
if (p <= 2) return 1;
if ((l = (char *)malloc(p)) == NULL) return -1;
if ((m = (char *)malloc(p)) == NULL) {
free(l);
return -1;
}

for (lp = l + p; lp != l; ) *--lp = 0;
*(l+2) = 1; /* L(1) = 4 */
for (i = 2; i < p; i++) {
for (lp = l + p, mp1 = m + p; lp != l; ) {
*--mp1 = *--lp;
*lp = 1; /* 2^p -1 mod 2^p -1 = 0 */
}
*(l+1) = 0; /* L(i) = L(i) - 2 */
for (mp1 = m, j = 0; j < p; j++) {
if (*mp1++) { /* this bit is 1 */
ca = 0;
k = j;
for (mp2 = m; mp2 != m + p; ) { /* L(i) * L(i) */
x = *mp2++ + *(l+k) + ca;
*(l+k) = x & 1;
ca = x >> 1;
if (++k == p) k = 0;
}
if (ca) {
while (*(l+k)) {
*(l+k) = 0;
if (++k == p) k = 0;
}
*(l+k) = 1;
}
}
}
}

x = *l;
for (lp = l + p; lp != l; ) /* L(p-1) == all 0 or 1 ? */
if (*--lp != x) {
ret = 0;
break;
}
free(m);
free(l);
return ret;
}

Ｃ言語は俺に聞けスレから来ました。
えー、上のプログラムはメルセンヌ素数のルカステストを行う関数なのですが
これが早いのか遅いのか私には判断がつきません。
ルカステストというのは、最速のアルゴリズムだとして、（まぁ普通のパソコンでＣＰＵ１Ｇ）
ぐらいのパソコンでどのくらいかかるのでしょか？
ちなみに自宅のパソコンで（ＣＰＵ５００Ｍぐらい）、2^3217のチェックが５分ほどかかりました。
誰か見てますかー？

>>493
500MHz から 1GHz になれば倍くらいの速度にはなるんじゃね？
恐らくCPUの世代も変わってるだろうからさらに早くなってるかもしれないし
コンパイラが違えば速度も変わるだろ？
で、何が知りたいの？

>>494
ＧＩＭＰＳのアプリケーションで2^11213-1のチェックでどのくらいかかるんでしょうか？

>>495
追加、要するに、パソコンの速さは気にせずに、上のコードが
早いのか遅いのか知りたいわけです。
ＦＦＴとか、あと、割り算をしなくていい方法とかあるようですが、
そういうの積んでいないもので、ちゃんとしたプログラムはどれく
らい早いのかなぁと思いまして

#0:　 　　　　　　　　1
1:　　　　　　　　　1　 1
2:　　　　　　　　1　 2　 1
3:　　　　　　　1　 3　 3　 1
4:　　　　　　1　 4　 6　 4　 1
5:　　　　　1　 5　10　10　5　1
6:　　　　1　 6　15　20　15 6　1
7:　　　1　 7　21　35　35 21 7　1

nは奇数とする。
1次項から(n-1)/2次項までの係数を評価すればよし
第m次項の係数は(1≦m≦(n-1)/2)　n C m =n(n-1)(n-2)(n-3)…(n-m)/1*2*3*…m
あぁ、自分なりに考えてみたけど。計算量が膨大すぎ。

↑に書いたピラミッドはあんまり意味ない(途中で気が変わったため不使用
暇なんで↑の方法使ったプログラム組んでみるわ（アホ

Qi Cheng,
``Primality Proving via One Round in ECPP and One Iteration in AKS,'' Crypto 2003
で少し高速化されたらしいです．age

しっかしここの>>1はよほどのアホだな。
「素数判定が多項式時間で可能！」なんて記事をちょっと学があるやつが見たら
「ぉ！鍵生成が楽になるな」って思うのが普通だろ…

まかに間違っても
「暗号総崩れ」などという奇天烈な発想にはつながらんはずだが…

ああ2年程前よくそんなレスを見たよ。