500コメント157KB

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

■ このスレッドは過去ログ倉庫に格納されています

0001デフォルトの名無しさん

NGNG

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

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

0002デフォルトの名無しさん

NGNG

出たなインド人

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

0003デフォルトの名無しさん

NGNG

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

0004デフォルトの名無しさん

NGNG

コリア困った

0005デフォルトの名無しさん

NGNG

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

0006デフォルトの名無しさん

NGNG

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

0007デフォルトの名無しさん

NGNG

そっすか！ｱｲｺﾞｰ！

0008デフォルトの名無しさん

NGNG

タコ式自慰で化膿？

0009デフォルトの名無しさん

NGNG

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

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

0010デフォルトの名無しさん

NGNG

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

0011デフォルトの名無しさん

NGNG

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

0012デフォルトの名無しさん

NGNG

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

0013デフォルトの名無しさん

NGNG

カンプールのインド工科大学の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

0014デフォルトの名無しさん

NGNG

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

0015デフォルトの名無しさん

NGNG

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

0016デフォルトの名無しさん

NGNG

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

0017デフォルトの名無しさん

NGNG

coprime って何?

0018デフォルトの名無しさん

NGNG

誰か完成してみて

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;

0019デフォルトの名無しさん

NGNG

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

0020デフォルトの名無しさん

NGNG

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

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;

0021デフォルトの名無しさん

NGNG

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

0022デフォルトの名無しさん

NGNG

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) 再帰こんな感じ?

0023デフォルトの名無しさん

NGNG

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

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

>>21
>>9

0024ずれた

NGNG

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) 再帰
こんな感じ?

0025デフォルトの名無しさん

NGNG

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

0026デフォルトの名無しさん

NGNG

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

0027デフォルトの名無しさん

NGNG

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

0028デフォルトの名無しさん

NGNG

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

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

0029デフォルトの名無しさん

NGNG

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

0030デフォルトの名無しさん

NGNG

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;

0031デフォルトの名無しさん

NGNG

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

0032デフォルトの名無しさん

NGNG

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

003325

NGNG

>>29
そう、それ。

0034デフォルトの名無しさん

NGNG

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

0035Rina ◆tI333vNE

NGNG

#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) {
* でいいんかな?
*/

0036デフォルトの名無しさん

NGNG

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;

0037デフォルトの名無しさん

NGNG

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

0038デフォルトの名無しさん

NGNG

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

0039デフォルトの名無しさん

NGNG

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

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

0040デフォルトの名無しさん

NGNG

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

0041デフォルトの名無しさん

NGNG

途中のループの

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;

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

0042デフォルトの名無しさん

NGNG

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

0043デフォルトの名無しさん

NGNG

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

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

0044Rina ◆tI333vNE

NGNG

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

0045余弦sy

NGNG

>>37
x=a=2と置け

0046Rina ◆tI333vNE

NGNG

#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;
}

0047デフォルトの名無しさん

NGNG

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

0048デフォルトの名無しさん

NGNG

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

0049デフォルトの名無しさん

NGNG

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

0050デフォルトの名無しさん

NGNG

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

0051デフォルトの名無しさん

NGNG

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

0052デフォルトの名無しさん

NGNG

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

0053デフォルトの名無しさん

NGNG

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

0054デフォルトの名無しさん

NGNG

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

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

0055デフォルトの名無しさん

NGNG

>>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
って意味じゃないのか?

0056デフォルトの名無しさん

NGNG

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

0057デフォルトの名無しさん

NGNG

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

0058Rina ◆tI333vNE

NGNG

もう書き込めないっぽ…行数が….
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;
}

0059デフォルトの名無しさん

NGNG

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

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

0060デフォルトの名無しさん

NGNG

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

0061デフォルトの名無しさん

NGNG

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

0062デフォルトの名無しさん

NGNG

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

0063デフォルトの名無しさん

NGNG

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

0064デフォルトの名無しさん

NGNG

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

・・・みたいな。

0065デフォルトの名無しさん

NGNG

結局12行目のxって何?

0066デフォルトの名無しさん

NGNG

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

0067デフォルトの名無しさん

NGNG

>>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;
間違いれした。

0068デフォルトの名無しさん

NGNG

>>65
多項式の変数

0069デフォルトの名無しさん

NGNG

結局

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

でいいの？

0070デフォルトの名無しさん

NGNG

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

0071デフォルトの名無しさん

NGNG

>>65
ｴｯｸｽ

0072デフォルトの名無しさん

NGNG

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

違ってたらｿﾏｿ

0073デフォルトの名無しさん

NGNG

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

0074デフォルトの名無しさん

NGNG

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

0075デフォルトの名無しさん

NGNG

と思う

0076デフォルトの名無しさん

NGNG

(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の約数ではないという条件だけでよいのではないか
といっている。

0077デフォルトの名無しさん

NGNG

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

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

0078デフォルトの名無しさん

NGNG

>>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個だけですむ。

0079デフォルトの名無しさん

NGNG

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

0080デフォルトの名無しさん

NGNG

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

0081デフォルトの名無しさん

NGNG

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

0082デフォルトの名無しさん

NGNG

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

0083デフォルトの名無しさん

NGNG

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

0084デフォルトの名無しさん

NGNG

>>81 NTTのEPOCとか。

0085デフォルトの名無しさん

NGNG

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

0086デフォルトの名無しさん

NGNG

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

008782

NGNG

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

0088７９

NGNG

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

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

0089デフォルトの名無しさん

NGNG

おしえて。

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

0090.

NGNG

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

0091デフォルトの名無しさん

NGNG

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

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

0092デフォルトの名無しさん

NGNG

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

0093デフォルトの名無しさん

NGNG

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

0094デフォルトの名無しさん

NGNG

>>85
禿同ﾊｧﾊｧ

0095デフォルトの名無しさん

NGNG

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

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

0096デフォルトの名無しさん

NGNG

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

0097デフォルトの名無しさん

NGNG

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

0098デフォルトの名無しさん

NGNG

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

0099デフォルトの名無しさん

NGNG

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

0100デフォルトの名無しさん

NGNG

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

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

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

0101デフォルトの名無しさん

NGNG

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

0102デフォルトの名無しさん

NGNG

>>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)でできる素数判定が書いてあるみたい

0103デフォルトの名無しさん

NGNG

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

0104デフォルトの名無しさん

NGNG

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

0105デフォルトの名無しさん

NGNG

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

0106デフォルトの名無しさん

NGNG

>>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だけをチェックするだけで素数判定できるだろう
という擬判定にしておいたらいいのでは。

0107デフォルトの名無しさん

NGNG

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

0108デフォルトの名無しさん

NGNG

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

a_k x^k

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

0109デフォルトの名無しさん

NGNG

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

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

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

0110デフォルトの名無しさん

NGNG

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

0111デフォルトの名無しさん

NGNG

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

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.は全然想像もできん。お前ら数学の定理かなんか知ってたら教えてくり。

0112デフォルトの名無しさん

NGNG

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

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

0113デフォルトの名無しさん

NGNG

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

0114デフォルトの名無しさん

NGNG

>>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の範囲がうまく押さえられているから
多項式時間でできることがわかったということだと思うよ。

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

0115デフォルトの名無しさん

NGNG

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

0116親切な人

NGNG

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

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

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

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

0117汎用機らー

NGNG

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

0118デフォルトの名無しさん

NGNG

>>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だけど具体的なアルゴリズムは知らんので私には書けないよん。

0119デフォルトの名無しさん

NGNG

>>117
いらねーよ。

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

0120デフォルトの名無しさん

NGNG

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

0121デフォルトの名無しさん

NGNG

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

0122デフォルトの名無しさん

NGNG

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

0123106

NGNG

>>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)よりはるかに小さいから無視できると。

0124デフォルトの名無しさん

NGNG

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

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

0125逝って良しの１

NGNG

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

0126逝って良しの１

NGNG

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

0127デフォルトの名無しさん

NGNG

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

0128デフォルトの名無しさん

NGNG

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

0129デフォルトの名無しさん

NGNG

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

0130106

NGNG

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

0131デフォルトの名無しさん

NGNG

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

01321

NGNG

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

0133デフォルトの名無しさん

NGNG

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

0134デフォルトの名無しさん

NGNG

>>132
偽者お疲れ

0135コピペ

NGNG

#!/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)}

0136デフォルトの名無しさん

NGNG

>>134そこ、反応しない

0137デフォルトの名無しさん

NGNG

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

0138デフォルトの名無しさん

NGNG

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

0139デフォルトの名無しさん

NGNG

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

0140逝って良しの１

NGNG

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

0141106

NGNG

>>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ならよい。

0142デフォルトの名無しさん

NGNG

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

0143デフォルトの名無しさん

NGNG

すんまそん。力技です。

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 回登場しますもんね。

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

0144デフォルトの名無しさん

NGNG

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

0145デフォルトの名無しさん

NGNG

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

0146デフォルトの名無しさん

NGNG

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

0147143

NGNG

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

0148143

NGNG

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

0149デフォルトの名無しさん

NGNG

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

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

0150デフォルトの名無しさん

NGNG

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

0151デフォルトの名無しさん

NGNG

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

0152逝って良しの１

NGNG

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

0153デフォルトの名無しさん

NGNG

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

0154143

NGNG

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

0155デフォルトの名無しさん

NGNG

まだ。

0156デフォルトの名無しさん

NGNG

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

0157デフォルトの名無しさん

NGNG

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

0158143

NGNG

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

0159143

NGNG

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

0160デフォルトの名無しさん

NGNG

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

0161143

NGNG

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

0162137

NGNG

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

// 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);
}

0163デフォルトの名無しさん

NGNG

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

0164デフォルトの名無しさん

NGNG

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

0165デフォルトの名無しさん

NGNG

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

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

01662.718@ニュー速+

NGNG

>>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);
とかしないと。

0167デフォルトの名無しさん

NGNG

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

0168デフォルトの名無しさん

NGNG

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

0169デフォルトの名無しさん

NGNG

>>167
神様は寝ました。

0170デフォルトの名無しさん

NGNG

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

0171デフォルトの名無しさん

NGNG

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

0172デフォルトの名無しさん

NGNG

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

0173デフォルトの名無しさん

NGNG

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

0174デフォルトの名無しさん

NGNG

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

0175デフォルトの名無しさん

NGNG

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

0176 ◆namco08.

NGNG

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

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

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

0177デフォルトの名無しさん

NGNG

namco

swap
↓ ↓
n a m c o

m a n c o

manco

(・∀・)ﾏﾝｺｰ

0178デフォルトの名無しさん

NGNG

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

0179デフォルトの名無しさん

NGNG

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

0180デフォルトの名無しさん

NGNG

スマソ、

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

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

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

0181デフォルトの名無しさん

NGNG

>>180
髭しくガイシュツ

0182137

NGNG

んー、作ってみたけど、どうもまともに動いてないようです。
もう眠いのでビール飲んで寝まふ。
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の方法を使えばかなり改善できそう？だけど難しすぎて降参しました。

0183デフォルトの名無しさん

NGNG

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;

0184デフォルトの名無しさん

NGNG

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

0185デフォルトの名無しさん

NGNG

仕事してください

0186逝って良しの１

NGNG

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

0187108

NGNG

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

0188デフォルトの名無しさん

NGNG

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

0189デフォルトの名無しさん

NGNG

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

0190デフォルトの名無しさん

NGNG

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

0191デフォルトの名無しさん

NGNG

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

0192C_sugar

NGNG

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

といってみるテスト。

0193デフォルトの名無しさん

NGNG

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

0194デフォルトの名無しさん

NGNG

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

0195デフォルトの名無しさん

NGNG

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

0196デフォルトの名無しさん

NGNG

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

0197デフォルトの名無しさん

NGNG

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

0198デフォルトの名無しさん

NGNG

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

0199デフォルトの名無しさん

NGNG

＞僕ら
おれはちゃうよ

0200デフォルトの名無しさん

NGNG

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

0201デフォルトの名無しさん

NGNG

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

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

ってま具合になるだろ？

0202デフォルトの名無しさん

NGNG

ってま

0203デフォルトの名無しさん

NGNG

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

0204デフォルトの名無しさん

NGNG

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

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

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

0205デフォルトの名無しさん

NGNG

>>204
ここは？

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

0206デフォルトの名無しさん

NGNG

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

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

0207デフォルトの名無しさん

NGNG

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

0208デフォルトの名無しさん

NGNG

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

0209デフォルトの名無しさん

NGNG

#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がやっている無意味な確認作業を完全に飛ばすための
プログラム。もともとＯＳはＣＰＵのパワーを自主的に抑えて
メモリーへの書き込みも無意味な制御を行っているが、
それをすべて解除するもの。だからＣＰＵ自体のスピードは変わらないが、
ＯＳからみたＣＰＵのスピードは２００％以上になる。
実際にＰ４の２．５Ｇで試したけど、６Ｇとりあえず認識してベンチマークでも
ちゃんとアップしていた。やってみな。

0210デフォルトの名無しさん

NGNG

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

0211デフォルトの名無しさん

NGNG

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

0212デフォルトの名無しさん

NGNG

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

0213デフォルトの名無しさん

NGNG

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

0214デフォルトの名無しさん

NGNG

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

0215デフォルトの名無しさん

NGNG

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

0216逝って良しの１

NGNG

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

0217デフォルトの名無しさん

NGNG

100100000001010000100001001は素数である

0218a

NGNG

>>209

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

0219a

NGNG

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

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

0220デフォルトの名無しさん

NGNG

（　´,_ゝ`）ﾌﾟｯ

0221デフォルトの名無しさん

NGNG

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

0222デフォルトの名無しさん

NGNG

>>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いじってたらできるんじゃないの？って思って
作ったら見事に動いた。しかももう、２年以上使っているけど、
ぜんぜん支障なし。気のせいか、無駄な青色画面も見ないですんでた。
まぁ、だまされたと思ってやってみな

0223デフォルトの名無しさん

NGNG

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

0224デフォルトの名無しさん

NGNG

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

0225デフォルトの名無しさん

NGNG

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

0226a

NGNG

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

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

0227デフォルトの名無しさん

NGNG

先生悲しいです

0228デフォルトの名無しさん

NGNG

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

0229デフォルトの名無しさん

NGNG

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

0230デフォルトの名無しさん

NGNG

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

0231デフォルトの名無しさん

NGNG

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

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

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

0232厨房２号 ◆OjTjK0LY

NGNG

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

0233厨房２号 ◆OjTjK0LY

NGNG

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

0234デフォルトの名無しさん

NGNG

幸運の壺か…

0235デフォルトの名無しさん

NGNG

俺もやってみよう

0236デフォルトの名無しさん

NGNG

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

0237デフォルトの名無しさん

NGNG

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

　　　　　２ｃｈの夏。厨房の夏。

0238デフォルトの名無しさん

NGNG

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

0239デフォルトの名無しさん

NGNG

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

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

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

0240デフォルトの名無しさん

NGNG

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

0241デフォルトの名無しさん

NGNG

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

0242厨房２号 ◆OjTjK0LY

NGNG

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

0243デフォルトの名無しさん

NGNG

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

0244デフォルトの名無しさん

NGNG

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

0245デフォルトの名無しさん

NGNG

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

0246デフォルトの名無しさん

NGNG

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

0247デフォルトの名無しさん

NGNG

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

0248デフォルトの名無しさん

NGNG

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

0249デフォルトの名無しさん

NGNG

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

0250デフォルトの名無しさん

NGNG

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

0251デフォルトの名無しさん

NGNG

>>244
ﾜﾗﾀ

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

0252デフォルトの名無しさん

NGNG

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

0253デフォルトの名無しさん

NGNG

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

0254デフォルトの名無しさん

NGNG

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

0255逝って良しの１

NGNG

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

0256デフォルトの名無しさん

NGNG

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

0257デフォルトの名無しさん

NGNG

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

0258デフォルトの名無しさん

NGNG

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

0259デフォルトの名無しさん

NGNG

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

0260デフォルトの名無しさん

NGNG

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

0261デフォルトの名無しさん

NGNG

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

0262デフォルトの名無しさん

NGNG

ｽﾚﾀｲよくないな…

0263デフォルトの名無しさん

NGNG

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

0264デフォルトの名無しさん

NGNG

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

0265デフォルトの名無しさん

NGNG

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

0266 ◆.RANK1Kg

NGNG

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

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

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

0267263

NGNG

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

0268逝って良しの１

NGNG

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

0269デフォルトの名無しさん

NGNG

>>268
既出

0270デフォルトの名無しさん

NGNG

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

0271デフォルトの名無しさん

NGNG

>>270
どれ？って？

0272デフォルトの名無しさん

NGNG

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

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

0273270

NGNG

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

0274デフォルトの名無しさん

NGNG

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

0275デフォルトの名無しさん

NGNG

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

0276デフォルトの名無しさん

NGNG

>>275
>>273

0277デフォルトの名無しさん

NGNG

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

0278デフォルトの名無しさん

NGNG

>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だけで正しい気がするよね。

0279デフォルトの名無しさん

NGNG

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

0280デフォルトの名無しさん

NGNG

フェルマーの小定理使えば(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)
って論文を最適化してどうする(´д`ゞ

0281デフォルトの名無しさん

NGNG

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

0282デフォルトの名無しさん

NGNG

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

0283デフォルトの名無しさん

NGNG

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

0284ああぁ？ageてやるよ

NGNG

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

0285デフォルトの名無しさん

NGNG

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

0286デフォルトの名無しさん

NGNG

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

0287デフォルトの名無しさん

NGNG

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

0288デフォルトの名無しさん

NGNG

JavaのBigIntegerについて。

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

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

0289デフォルトの名無しさん

NGNG

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

0290デフォルトの名無しさん

NGNG

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

0291266 ◆.RANK1Kg

NGNG

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

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

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

0292デフォルトの名無しさん

NGNG

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;
}

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

0293デフォルトの名無しさん

NGNG

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

0294デフォルトの名無しさん

NGNG

>>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 な方法が見つかった今となっては
さほど興味深い話ではないだろうけど。

0295292

NGNG

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

0296デフォルトの名無しさん

NGNG

実際には多倍長でしょ。

0297 ◆.RANK1Kg

NGNG

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

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

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

0298息抜きに作りました

NGNG

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;
}

0299デフォルトの名無しさん

NGNG

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

0300デフォルトの名無しさん

NGNG

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

0301デフォルトの名無しさん

NGNG

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

0302名無しさん＠Ｅｍａｃｓ

NGNG

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

0303デフォルトの名無しさん

NGNG

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 の倍数であるという前提

0304デフォルトの名無しさん

NGNG

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

0305 ◆.RANK1Kg

NGNG

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

0306デフォルトの名無しさん

NGNG

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

0307デフォルトの名無しさん

NGNG

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

0308デフォルトの名無しさん

NGNG

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

0309デフォルトの名無しさん

NGNG

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

0310デフォルトの名無しさん

NGNG

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

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

0311デフォルトの名無しさん

NGNG

つかMATLAB2Cがあるだろ

0312デフォルトの名無しさん

NGNG

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

0313デフォルトの名無しさん

NGNG

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

0314デフォルトの名無しさん

NGNG

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

難しいのはそこだけだ。

0315デフォルトの名無しさん

NGNG

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

0316デフォルトの名無しさん

NGNG

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

0317デフォルトの名無しさん

NGNG

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

0318デフォルトの名無しさん

NGNG

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

0319一休

NGNG

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

0320デフォルトの名無しさん

NGNG

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

0321デフォルトの名無しさん

NGNG

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

0322デフォルトの名無しさん

NGNG

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

0323デフォルトの名無しさん

NGNG

>>321
>>311

0324デフォルトの名無しさん

NGNG

>>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飛びに足し合わせればいい。

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

03251/3

NGNG

(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;

03262/3

NGNG

---
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へジャンプ。
-----

03273/3

NGNG

判定

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

0328デフォルトの名無しさん

NGNG

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

0329デフォルトの名無しさん

NGNG

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のやり方ですな。

0330デフォルトの名無しさん

NGNG

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

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

0331デフォルトの名無しさん

NGNG

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

0332デフォルトの名無しさん

NGNG

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

0333デフォルトの名無しさん

NGNG

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

0334デフォルトの名無しさん

NGNG

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

0335デフォルトの名無しさん

NGNG

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

0336デフォルトの名無しさん

NGNG

>2=>1

0337息抜き 1/2

NGNG

>>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;
}

0338息抜き 2/2

NGNG

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;
　}
}

0339デフォルトの名無しさん

NGNG

mul引数のrとn逆だった

0340デフォルトの名無しさん

NGNG

>>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++) {

0341デフォルトの名無しさん

NGNG

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

0342デフォルトの名無しさん

NGNG

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;

0343デフォルトの名無しさん

NGNG

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;

ですね。

0344デフォルトの名無しさん

NGNG

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

0345デフォルトの名無しさん

NGNG

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

03461/2

NGNG

こうなのか。

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;
}

03472/2

NGNG

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;
　}
}

0348デフォルトの名無しさん

NGNG

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

0349デフォルトの名無しさん

NGNG

この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)
まぁ、多項式だから良しとしてくれぇ。

0350デフォルトの名無しさん

NGNG

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

0351デフォルトの名無しさん

NGNG

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

0352一部抜粋

NGNG

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

0353デフォルトの名無しさん

NGNG

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

0354デフォルトの名無しさん

NGNG

>>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に等しくなるかで判定するのかなぁ。

0355デフォルトの名無しさん

NGNG

>>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;
}

0356デフォルトの名無しさん

NGNG

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

0357デフォルトの名無しさん

NGNG

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

0358デフォルトの名無しさん

NGNG

>>357
c2ruby

0359デフォルトの名無しさん

NGNG

0360デフォルトの名無しさん

NGNG

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

0361デフォルトの名無しさん

NGNG

頭だけ回ってる。

0362デフォルトの名無しさん

NGNG

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

0363デフォルトの名無しさん

NGNG

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

0364デフォルトの名無しさん

NGNG

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

0365デフォルトの名無しさん

NGNG

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

0366デフォルトの名無しさん

NGNG

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

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

0367デフォルトの名無しさん

NGNG

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

0368デフォルトの名無しさん

NGNG

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

0369デフォルトの名無しさん

NGNG

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

0370デフォルトの名無しさん

NGNG

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

0371デフォルトの名無しさん

NGNG

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

0372デフォルトの名無しさん

NGNG

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

0373デフォルトの名無しさん

NGNG

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

0374デフォルトの名無しさん

NGNG

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

0375デフォルトの名無しさん

NGNG

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

0376デフォルトの名無しさん

NGNG

あきらめたのか？

0377デフォルトの名無しさん

NGNG

あきたんだと思う

0378デフォルトの名無しさん

NGNG

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

0379デフォルトの名無しさん

NGNG

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

0380デフォルトの名無しさん

NGNG

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

0381デフォルトの名無しさん

NGNG

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

0382デフォルトの名無しさん

NGNG

あげ

0383デフォルトの名無しさん

NGNG

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

0384デフォルトの名無しさん

NGNG

すごい理屈だ

0385デフォルトの名無しさん

NGNG

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

0386デフォルトの名無しさん

NGNG

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

0387デフォルトの名無しさん

NGNG

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

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

0388デフォルトの名無しさん

NGNG

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

0389デフォルトの名無しさん

NGNG

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

0390デフォルトの名無しさん

NGNG

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

0391デフォルトの名無しさん

NGNG

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

0392デフォルトの名無しさん

NGNG

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

0393デフォルトの名無しさん

NGNG

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

0394デフォルトの名無しさん

NGNG

>>393
へー

0395デフォルトの名無しさん

NGNG

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

0396デフォルトの名無しさん

NGNG

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

0397デフォルトの名無しさん

NGNG

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

0398デフォルトの名無しさん

NGNG

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

0399デフォルトの名無しさん

NGNG

>>398 2n+1

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

0400デフォルトの名無しさん

NGNG

age

0401namahage

NGNG

namahage

0402デフォルトの名無しさん

NGNG

ﾌﾟｯﾁ神父に聞こう

0403デフォルトの名無しさん

NGNG

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

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

0404デフォルトの名無しさん

NGNG

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

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

0405858じゃないけど

NGNG

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

0406デフォルトの名無しさん

NGNG

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

0407デフォルトの名無しさん

NGNG

>>406
segmentation fault で止まる。

0408デフォルトの名無しさん

NGNG

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

0409デフォルトの名無しさん

NGNG

ほっしゅ

0410デフォルトの名無しさん

NGNG

OO 最高

0411デフォルトの名無しさん

NGNG

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

0412デフォルトの名無しさん

NGNG

.NET 最高

0413デフォルトの名無しさん

NGNG

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

0414デフォルトの名無しさん

NGNG

ところで、

0415デフォルトの名無しさん

NGNG

何よ

0416デフォルトの名無しさん

NGNG

実は

0417デフォルトの名無しさん

NGNG

…実は？

0418デフォルトの名無しさん

NGNG

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

0419こう、男の指でぐりぐりと

NGNG

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

0420デフォルトの名無しさん

NGNG

保守・

0421デフォルトの名無しさん

NGNG

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

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

0422419

NGNG

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

0423IP記録実験

NGNG

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を提出することがある。

0424デフォルトの名無しさん

NGNG

じっけん　じっけん

0425デフォルトの名無しさん

NGNG

>>315　ﾌﾟ

0426デフォルトの名無しさん

NGNG

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

0427デフォルトの名無しさん

NGNG

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

0428デフォルトの名無しさん

NGNG

漢ならあえて晒す。

0429IP記録実験

NGNG

0430デフォルトの名無しさん

NGNG

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

0431デフォルトの名無しさん

NGNG

記録されますた！

0432デフォルトの名無しさん

NGNG

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

0433デフォルトの名無しさん

NGNG

======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
────────────────────────────

0434デフォルトの名無しさん

NGNG

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

0435デフォルトの名無しさん

NGNG

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

0436デフォルトの名無しさん

NGNG

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

0437デフォルトの名無しさん

NGNG

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

0438デフォルトの名無しさん

NGNG

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

0439デフォルトの名無しさん

NGNG

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

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

0440デフォルトの名無しさん

NGNG

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

0441デフォルトの名無しさん

NGNG

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

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

0442デフォルトの名無しさん

NGNG

《一覧表》

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

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

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

0443デフォルトの名無しさん

NGNG

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

0444デフォルトの名無しさん

NGNG

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

0445デフォルトの名無しさん

NGNG

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

0446デフォルトの名無しさん

NGNG

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

0447デフォルトの名無しさん

NGNG

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

0448デフォルトの名無しさん

NGNG

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

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

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

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

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

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

んじゃ！

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

0449デフォルトの名無しさん

NGNG

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

0450デフォルトの名無しさん

NGNG

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

0451デフォルトの名無しさん

NGNG

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

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

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

0452デフォルトの名無しさん

NGNG

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

0453デフォルトの名無しさん

NGNG

コリア困った

0454デフォルトの名無しさん

NGNG

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

0455デフォルトの名無しさん

NGNG

(^^)

0456デフォルトの名無しさん

NGNG

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

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

0457デフォルトの名無しさん

NGNG

600,000,088

0458デフォルトの名無しさん

NGNG

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

0459デフォルトの名無しさん

NGNG

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

0460デフォルトの名無しさん

NGNG

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

0461デフォルトの名無しさん

NGNG

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

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

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

0462デフォルトの名無しさん

NGNG

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

0463デフォルトの名無しさん

NGNG

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

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

0464デフォルトの名無しさん

NGNG

くすぐり攻撃。

まぁ　火曜日までには、

0465qwert

NGNG

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言語で書いて下さい。

0466デフォルトの名無しさん

NGNG

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

0467山崎渉

NGNG

（＾＾）

0468デフォルトの名無しさん

NGNG

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

0469山崎渉

NGNG

（＾＾）

0470山崎渉

NGNG

（＾＾）

0471デフォルトの名無しさん

NGNG

結局どうなった？

0472デフォルトの名無しさん

NGNG

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

0473デフォルトの名無しさん

NGNG

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

0474デフォルトの名無しさん

NGNG

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

0475デフォルトの名無しさん

NGNG

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

0476デフォルトの名無しさん

NGNG

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

0477山崎渉

NGNG

（＾＾）

0478山崎渉

NGNG

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

0479デフォルトの名無しさん

NGNG

…実は?

0480山崎渉

NGNG

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

0481山崎渉

NGNG

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

0482age

NGNG

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

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

0483デフォルトの名無しさん

NGNG

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

0484デフォルトの名無しさん

NGNG

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

0485デフォルトの名無しさん

NGNG

>>484
　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　´_ゝ`

0486デフォルトの名無しさん

NGNG

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

0487デフォルトの名無しさん

NGNG

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

0488コヨーテ

NGNG

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

0489山崎渉

NGNG

（＾＾）

0490山崎渉

NGNG

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

0491age

NGNG

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;
}

0492age

NGNG

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;
}
}
}
}

0493age

NGNG

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のチェックが５分ほどかかりました。
誰か見てますかー？

0494デフォルトの名無しさん

NGNG

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

0495age

NGNG

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

0496age

NGNG

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

0497デフォルトの名無しさん

NGNG

#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
あぁ、自分なりに考えてみたけど。計算量が膨大すぎ。

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

0498デフォルトの名無しさん

NGNG

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

0499デフォルトの名無しさん

NGNG

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

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

0500デフォルトの名無しさん

NGNG

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

■ このスレッドは過去ログ倉庫に格納されています