トップページ⇒tech
500コメント157KB

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

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明
http://news2.2ch.net/test/read.cgi/newsplus/1028876818/

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

0153デフォルトの名無しさんNGNG
　　　　　　　　∧＿∧
　　　　　　　 （ ´Д｀ ） ＜　>>150 漏れに何ができるって言うんだ！
　　　　　　　／,　　/
　　　　　　(ぃ９　　|
0154143NGNG
>>143 早速バグ発見
例に出した数値 2744 からして a^b だと認めてくれないです（笑い
0155デフォルトの名無しさんNGNG
まだ。
0156デフォルトの名無しさんNGNG
>>152
「気合入れれば、力技でいける」の意
0157デフォルトの名無しさんNGNG
HSPに書き直して何に使う気よ？
0158143NGNG
>>154 で見つけたバグを早速fix
  i = 6 - i; // 4 と 2 を交互に
の行をコメントアウトすればｲｯﾊﾟﾂですた。
でもできるだけ効率的に素数を探しながら因数分解したいんで
改良しなきゃ～・・・
0159143NGNG
ともかく>>143はマトモに素因数分解してるのでネタということで。
んーと，a^b であるか否かを判定するのは P 問題なんですか？
0160デフォルトの名無しさんNGNG
　_________
/∴∵∴ヽ
|∵∴∞ヽ|　 ＿＿＿＿＿＿＿＿＿
|∴/= ♀=| <漏前ら寝るんじゃねぇ
＼| 　 ▽/　 ￣￣￣￣￣￣￣￣￣
　　￣￣
0161143NGNG
あーもう頭がアレになってきた
私は眠いので寝ます・・・
0162137NGNG
途中。変数の宣言なし。
今から多項式の割り算をやってみる。

// 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
髭しくガイシュツ
0182137NGNG
んー、作ってみたけど、どうもまともに動いてないようです。
もう眠いのでビール飲んで寝まふ。
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
普通の会社は今日は休みです。
0187108NGNG
>>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_sugarNGNG
いずれにせよ、量子コンピュータが普及すれば今の暗号技術は使えなくなる分けであるし、
それもそう遠い未来ではない。

といってみるテスト。
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は素数である
0218aNGNG
>>209

win2000 sp3 でためしてみた、システム３２フォルダに入れて再起動、
するとどうだろう？vs.netの軌道時間がえらく短縮した。どうさもきびききびしてる。
せれ４００．しかし、このおれのきじゅつをみてためせばいいってもんじゃあない。
おれもいまこわいから、とにかくすげーーーーーーーーーーーーーーーーーーー
0219aNGNG
起動する世絶対にとは言わないが、おれはした。
俺は二台パソコンが合って、実験用のやつに入れているから、どうなっても気にせずにすむ。

そうでないやつは分析が出るまで待ったほうがよい絶対に
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
あふぉ？ｗ
ただでさえクソ重いのに自分から重くしてどーすんだよ…。
0226aNGNG
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ってどうすんねん。
■ このスレッドは過去ログ倉庫に格納されています