- 1 名前：デフォルトの名無しさん mailto:sage [2012/03/16(金) 19:44:28.87 ]
- エスケープシーケンスやWin32APIなどの環境依存なものでもOK。
ただしその場合、質問者は必ず環境を書きましょう。
※sage禁止です(と代々スレに書いてありますが自己判断で)。
【前スレ】
【初心者歓迎】C/C++室 Ver.77【環境依存OK】
toro.2ch.net/test/read.cgi/tech/1323692486/
◆ソースのインデントについて
半角空白やTABでのインデントはスレに貼ると無くなります。
そのため、アップローダーに上げるのも手ですが直接貼る場合は、
全角空白か に置換すると見栄えだけはよくなります。
【アップローダー】(質問が長い時はココ使うと便利)
codepad.org/ (コンパイルもできるし出力結果も得られる[]privateをチェック)
ideone.com/ (時間帯によってはcodepadが重い事があるのでここも利用)
- 237 名前：デフォルトの名無しさん mailto:sage [2012/05/05(土) 19:58:50.80 ]
- unsigned long r64;//random
for(int i = 0 ; i < 64 ; i++)
{
array[i] = (r64>>i)&0x01;
}
- 238 名前：デフォルトの名無しさん mailto:sage [2012/05/05(土) 20:07:44.12 ]
- >>236
そんな効率の悪そうなことをするためのコードが速くて本当に何か意味があるのかね？
- 239 名前： ◆QZaw55cn4c mailto:sage [2012/05/05(土) 20:21:03.06 ]
- 今求めているのは、
素数かどうか不明のものを素因数分解すること
ではなく
既知の巨大素数の原始根を求めること
なのですが？
うーん。全然わからん。
- 240 名前：デフォルトの名無しさん mailto:sage [2012/05/05(土) 20:37:55.62 ]
- 既知の分なら求めず表にするれ
- 241 名前：デフォルトの名無しさん [2012/05/05(土) 20:43:25.15 ]
- >>239
これ。
mod19の原始根をすべて求めよという問題があるのですがひとつひとつ表を埋めていく... - Yahoo!知恵袋
detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1235764892
- 242 名前：デフォルトの名無しさん [2012/05/05(土) 20:59:34.72 ]
- mod p での一般的な原始元を見つける方法
1.平方剰余の性質を使って平方非剰余の根aをみつけます。2.aが原始元でない場合は平方剰余の根bをaに掛けa×bを計算します。
mod p ではp-1と互いに素となる原始根のべき乗となるものを探すわけです。
mod 63823の原始元の求め方
第２補充法則 (2/p)＝(-1)^((p^2)-1)/8) より(-1)^((63823^2)-1)/8)＝1 で2は平方剰余
(q/p)(p/q)＝(-1)^( ((q-1)/2)×((p-1)/2) )を利用して、(3/63823)(63823/3)＝(3/63823)(1/3)＝-1 なので、３は平方非剰余
p-1＝63823-1＝2×3×11×967
3^(2×11×967)＝16721 で3次剰余ではない。3^(2×3×967)＝28107 で11次剰余ではない。3^(2×3×11)＝40828 で967次剰余ではない。
したがって3は原始根
detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1235764892
平方剰余の相互法則 - Wikipedia
a と p とが互いに素であるとき、合同式
upload.wikimedia.org/wikipedia/ja/math/9/3/1/9311f58ff72132d811ba22cdee7c8d9e.png
が解を持てば、 a は p を法として平方剰余であるといい、そうでないとき平方非剰余であるという。
(p, a) を a と p の最大公約数とするとき、次の記号
upload.wikimedia.org/wikipedia/ja/math/1/4/d/14d936e40558c1f206d4394943f794b6.png
を、アドリアン＝マリ・ルジャンドルにちなんでルジャンドル記号と呼ぶ。
[編集] 相互法則平方剰余の相互法則は整数 a が奇素数 p を法として平方剰余であるか否かを見いだす法則である。
p, q を相異なる奇素数とするときに、
upload.wikimedia.org/wikipedia/ja/math/b/c/b/bcb6ec45662135c3c218a771577e9ef7.png
が成り立つ。
また、このほかに以下の第1補充法則、第2補充法則が知られている。
第1補充法則:
upload.wikimedia.org/wikipedia/ja/math/d/f/3/df3f591f53cfc80bdea6e5d7e74db393.png
第2補充法則:
upload.wikimedia.org/wikipedia/ja/math/f/0/3/f03b9412c25ac66daef4571029a536a6.png
またpとa、bが素であれば、
upload.wikimedia.org/wikipedia/ja/math/7/9/0/790121bd3962a9abf69e1a69448e134d.png
- 243 名前：デフォルトの名無しさん [2012/05/05(土) 21:05:39.49 ]
- 原始根を見つけるのに平方剰余の相互法則を使うのは定番らしい。証明説明。
nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf
aozoragakuen.sakura.ne.jp/suuron/node41.html
www.geocities.jp/ikuro_kotaro/koramu/1548_p1.htm
pisan-dub.jp/doc/2011/20110114001/5_6.html
www004.upp.so-net.ne.jp/s_honma/algebra/algebra21.htm
- 244 名前：デフォルトの名無しさん mailto:sage [2012/05/05(土) 21:11:13.23 ]
- >>236
>>237のを使うぐらいしかないんじゃない？
それかいちいち計算せずに、関数を用意しておくとか？
int get_bit(ulong r64)
{
return (r64>>i)&0x01;
}
おそらく>>236のしようとしていることは非効率的で、
オリコウでない方法だと思うよ。
- 245 名前：デフォルトの名無しさん [2012/05/05(土) 21:21:22.96 ]
- 平方非剰余の数が原始根候補になり、素因数分解を使い原始根を確定させる。
奇素数 p を法とする原始根 g は p を法として平方非剰余である．
nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf
法997では、位数は996の約数になるので、ａが、997の原始根であることを確かめるには、996=2・2・3・83 に注意して、ａ^498≠1、ａ^332≠1、ａ^12≠1 かどうかを調べれば十分。
www004.upp.so-net.ne.jp/s_honma/algebra/algebra21.htm
- 246 名前：デフォルトの名無しさん [2012/05/05(土) 21:39:15.70 ]
- 素因数分解が出来ていれば全ての原始根も求められる。一つ見つかっていた場合。
detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1235764892
mod19の乗法群は位数18の巡回群になります。
18=2×3×3
なので 2, 3 と互いに素な原始元の冪乗は全て原始元になります。
原始元は{2,3,10,13,14,15}ですが、
このなかのどれか一つを選択してgとした場合
g,g^5,g^7,g^11,g^13,g^17
は全て原始元になります。
- 247 名前：デフォルトの名無しさん mailto:sage [2012/05/05(土) 22:08:34.97 ]
- >>244
別な方法で実装しました
要するに長い行列に対してm-sequenceでディザリングをしたかったのですが
後で処理をするためにディザリングの配列は残しておかねばなりません
なにかいい方法がありますか？
- 248 名前：デフォルトの名無しさん mailto:sage [2012/05/05(土) 23:29:30.87 ]
- ありますよ。ちょっと待って下さいね。
- 249 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/05(土) 23:43:14.24 ]
- n番目の素数の概算値Paは
Pa=2.32nlogn+2n
で大体出せた
- 250 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/05(土) 23:54:41.30 ]
- あ、調べたら
Pa=nlogn+nloglogn
って書いてた
- 251 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 00:02:10.05 ]
- 調べた方が精度悪いや
- 252 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 00:03:17.22 ]
- 荒らしかよtwitterか数学板にでも行けよ
- 253 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 10:44:31.59 ]
- >>252
さすがです
- 254 名前：デフォルトの名無しさん [2012/05/06(日) 11:00:33.25 ]
- >>239
すべての原始根をもとめるのに素因数分解なしで高速に求められるのがあるのか?
- 255 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 11:53:07.35 ]
- n番目の奇素数を正確に出す式あるだろバカか
- 256 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 13:04:47.55 ]
- あったら暗号が使えなくなるか
あっても指数時間の計算でしょ
- 257 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 13:19:19.66 ]
- 精度改良しましたが
Pa=2((0.45loglog(logn+0.25)+1.12)nlogn+n)
は多項式時間の概算計算す
- 258 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 13:56:39.90 ]
- 質問の意図や前提をくみ取れない糞質問
が多い。それで回答者が逆質問をしたり
悪口を言ったりする。それを前もって思
い描く力が絶望的に欠如してるに違いない。
スーパーハッカーだけが意図を理解できる。
レアなそういう神が颯爽と登場する予感。
- 259 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 14:24:03.05 ]
- 質問です
4年ほど前にやっていたことがあって、再度VisualStudio2008C++EEを落としてみたんですが、色々変わったんでしょうか？
講座サイトを見ながらやっているんですが、新規作成→追加で「C++ファイル」ではなく「C++クラス」と出てきてしまいます
試しに作ってみると、.cppに初めから何か書かれているんですが…
- 260 名前：デフォルトの名無しさん [2012/05/06(日) 14:26:27.52 ]
- 変わりなし。
嫌ならコマンドラインでコンパイルしたら良い。
- 261 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 14:26:55.62 ]
- 空のプロジェクトをチェックして
ソースファイルフォルダ右クリックで追加すればいい
- 262 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 14:30:54.14 ]
- ありがとうございます、助かりました！
.cppはその下に記述すれば良さそうですね。
- 263 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 14:51:55.93 ]
- n番目の素数の概算がでるから
その前後調べて当たったら暗号無効化なの？
- 264 名前：デフォルトの名無しさん [2012/05/06(日) 15:00:05.08 ]
- 素数の個数と、素因数分解は別だろ。
暗号解読では素因数が判明しないとダメだろ。
- 265 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 15:12:59.72 ]
- じゃあ、複二次式で四次篩作ればどうなん？
- 266 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 15:14:54.57 ]
- 素因数分解の結果をキャッシュしてるから、素因数分解なんか一瞬だ
- 267 名前：デフォルトの名無しさん [2012/05/06(日) 15:21:11.34 ]
- サルにもわかるＲＳＡ暗号: 解読法と素数
www.maitou.gr.jp/rsa/rsa14.php
- 268 名前：デフォルトの名無しさん [2012/05/06(日) 15:25:46.00 ]
- 無理。
2003 年の年末時点では素数と素数を掛けた数が 174 桁の数が、 100 台の業務用コンピュータで協調計算させて 3 ヶ月で素因数分解できることが実証されています。
一方、現在の ＲＳＡ暗号 では一般的には素数と素数を掛け合わせた後が 310 桁にもなる数を用いています。
これでは、現在の数学で巨大な素因数分解を行うには、神をも味方につけた超人的な運を手に入れるしかないでしょう。
確率的には、残念ながら競馬やパチンコ、宝くじとは比べ物になりません。
www.maitou.gr.jp/rsa/rsa14.php
- 269 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 15:55:01.73 ]
- >>247
聞いてきましたわ。
579 名前：デフォルトの名無しさん [sage]： 2012/05/06(日) 01:28:04.90
画像処理の質問ではないな。
unionって知ってる？
unsigned longをbit配列と同意義で読み替えてやればいい。組み込み系でよく使う手法だがや
580 名前：デフォルトの名無しさん [sage]： 2012/05/06(日) 04:42:09.66
>>578
ビットフィールドでググれ
581 名前：デフォルトの名無しさん [sage]： 2012/05/06(日) 04:44:12.99
ただ速くしたいなら素直にビット演算としてSIMDで書いたほうが速いだろ
- 270 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 16:28:18.94 ]
- x^4-a^4=(x^2+a^2)(x^2-a^2)
使って四次篩作れば
310桁は4桁計算だけど？
二次篩でも17桁
- 271 名前：デフォルトの名無しさん [2012/05/06(日) 16:31:58.50 ]
- しらねえが。
1024ビット=310桁の素因数分解が一定時間で安定して出来るアルゴリズムを開発したら
研究所や大学からお呼びがかかるだろう。
- 272 名前：デフォルトの名無しさん [2012/05/06(日) 16:41:15.73 ]
- NTTら、768ビット合成数を一般数体篩法にて完全分解に成功 2010/01/08
NTTは1月7日、スイス連邦工科大学ローザンヌ校(EPFL)、独ボン大学、フランス国立情報学自動制御研究所(INRIA)、オランダ国立情報工学・数学研究所(CWI)との共同研究により、
素因数分解問題において、従来の世界記録である663ビット(10進200桁)を上回る、
768ビット(10進 232桁)の合成数に対して、一般数体篩法による素因数分解を達成したことを発表した。
NTTらは今回、700ビットを超す素因数分解を達成したが、これは将来的にRSA暗号で使われている1024ビットの素因数分解も
達成される可能性があることを示唆することとなり、より高い強度かつ効率的な暗号技術を利用する必要性が高まることを意味する。
研究内容は、巨大な合成数に対して現段階で最も高速な解法として知られている一般数体篩法を用いて実施された。
篩処理は、全体の計算量の大半を占めるが、比較的容易に分散計算可能であることから多数の参加組織により並列に計算を行った。
処理は主にNTT研究所、EPFL、ボン大、INRIA、CWIにある多種多様のPCやクラスタを用い、
全体でおよそOpteron 2.2GHz換算で1,500年かけたのと同程度の計算量を要した。
また、理論的に最も計算料を要するステップの1つである線形代数は、分散計算が困難であり、今回は少数のクラスタを利用し、
それぞれのクラスタの速度や空き時間が異なっていても効率的に計算できる手法を開発・利用。
NTT研究所およびEPFLのクラスタ、またINRIAはフランスにあるALADDIN-G5Kを効率的に用い、
filteringで生成された疎行列からなる連立方程式を解いた。
Opteron 2.2GHz換算でおよそ155年の計算量を要した結果、分解に利用可能な解が得られたとする。
その結果、最終ステップとなる平方根(代数的数の平方根の計算及び最小公約数の計算)では、
EPFLに設置された計算機を用いることで、数時間で以下の解を得たという。
なお、同結果を受けてNTTでは、NTT研究所にて暗号技術全般の安全性を継続的に評価していくとするほか、
次世代暗号として楕円曲線上の演算規則を利用した新しい公開鍵暗号方式「楕円曲線暗号」の普及にも努めていくとしている。
news.mynavi.jp/news/2010/01/08/055/index.html
- 273 名前：デフォルトの名無しさん [2012/05/06(日) 16:49:32.43 ]
- 暗号アルゴリズムの危殆化
www.nic.ad.jp/ja/newsletter/No44/images/0800_8.gif
www.nic.ad.jp/ja/newsletter/No44/0800.html
NTTなど、公開鍵暗号の素因数分解問題で768ビット整数の分解に成功
分解に要した計算資源は1700コア・年としている。デュアルコアのCPUを搭載したコンピュータなら、850台程度あれば約1年で分解できる計算になる。
実際にはNTT情報流通プラットフォーム研究所など5研究機関は2007年から分解を始め、PCクラスターなど300台程度のコンピュータを用いて、約3年かかったという。
itpro.nikkeibp.co.jp/article/NEWS/20100108/343056/
ＮＴＴ、２３２ケタ整数の素因数分解に成功−世界記録を更新 現在使用の３０９ケタはあと１０年は大丈夫！
highsociety.at.webry.info/201001/article_33.html
- 274 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 16:57:07.10 ]
- ttp://www5b.biglobe.ne.jp/~NAS6/secret/index.htm
四次篩実装
2^n次篩も簡単に作れます
- 275 名前：デフォルトの名無しさん [2012/05/06(日) 17:09:31.65 ]
- 一般・特殊数体ふるい法が現在最速ってあるし実際の記録更新もそれだが。
素因数分解 - Wikipedia
2005年5月、200桁の合成数 RSA-200が素因数分解される（一般数体ふるい法、Bahr, Boehm, Franke, Kleinjung）
2006年8月、10381 + 1 から67桁の素数が分解される（楕円曲線法、B. Dodson）
2006年9月、7352 + 1 の約数として現れる128桁の合成数が素因数分解される（一般数体ふるい法、情報通信研究機構、富士通、富士通研究所）
2007年5月、21039 ^ 1の約数として現れる307桁の合成数が素因数分解される（特殊数体ふるい法、NTT、ドイツのボン大学、スイス連邦工科大学との共同研究）
2010年1月、232桁(768ビット）（NTT、スイス連邦工科大学ローザンヌ校(EPFL)、独ボン大学、フランス国立情報学自動制御研究所(INRIA)、オランダ国立情報工学・数学研究所(CWI)。一般数体ふるい法。300台PCの並列計算処理。約３年）
改訂多重基底多項式篩法(MBPS2、Multiple Base Polynomial Sieve 2nd)
2006年8月に考案したMBPSの改良版。
本方式で世界記録に挑戦する。原理プログラムを作成し、現在は試作プログラムの作成中
試作プログラムが完成すれば、ほぼ計算量の予測が可能であるが、本方式で数年以内に1024ビットの
RSA暗号の解読は可能になると思われる。
MBPS(多重基底多項式篩法)に対して、多項式f(x)を法とし、素イデアル基底で分解できるイデアルの積
で作られるイデアルも素イデアル基底で分解できる、特長を利用した方法。
www.cs.t-kougei.ac.jp/nsim/RSA.htm
GNFS176
2005年4月22日、我々のチーム(下記)は 11^281+1 の約数である 176桁の合成数を「一般数体ふるい法(GNFS)」で分解した。
www.rkmath.rikkyo.ac.jp/~kida/gnfs176.html
- 276 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 17:15:12.33 ]
- 一人だけでも生き残ろうと…未来貯蓄銀会長密航試み逮捕
営業停止審査を受けている未来貯蓄銀行のキム・チャンギョン会長が4日、中国へ密航しようとしていたところを、
仁川（インチョン）港で海上警察に逮捕されたとSBSが単独報道した。
報道によれば、海上警察は逮捕したキム会長の身柄を不良貯蓄銀行捜査を担当する、
貯蓄銀行不正合同捜査チームへ送る予定だと伝えられた。報道によればキム会長は、
5日午前8時に予定されていた貯蓄銀行経営評価委員会に出席して、
営業停止前に最後の意見を陳述するようにとの金融当局の通知を受けた後、
中国へ密かに渡航しようとしていたことが分かった。
一人だけでも生き残ろうと…未来貯蓄銀会長密航試み逮捕
韓国語 [05/05]
news.donga.com/Society/3/03/20120505/46025772/1
- 277 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 17:16:14.77 ]
- 2^n次篩で世界記録楽勝す
実験するのにはデータ型のビットを増やしたクラス作んなきゃ
ならないけどめんどい
- 278 名前：デフォルトの名無しさん [2012/05/06(日) 17:24:37.82 ]
- たとえば数分で可能な数で比較して、このソフトより速いんだったら少し信用する。
GGNFSはNFS法（the Number Field Sieve method; 数体ふるい法）を用いる素因数分解プログラムです。
SNFS法（特殊数体ふるい法）とGNFS法（ 一般数体ふるい法）の両方に対応しています。作者はChris Monicoさんです。
homepage2.nifty.com/m_kamada/math/ggnfs_ja.htm
- 279 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 17:35:01.58 ]
- なんか色々インストールしなきゃならないからやだな
Long long intなら確認済みだから良いや
- 280 名前：デフォルトの名無しさん [2012/05/06(日) 17:49:32.41 ]
- Windows Factoring Software Binaries (64bit & 32bit)
gilchrist.ca/jeff/factoring/index.html
gilchrist.ca/jeff/factoring/benchmark.html
gilchrist.ca/jeff/factoring/pseudoprimes.html
GGNFS suite プロジェクト日本語トップページ - SourceForge.JP
sourceforge.jp/projects/sfnet_ggnfs/
- 281 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 17:50:28.40 ]
- 調子にのって８乗してた訂正
- 282 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 19:08:31.98 ]
- 二次篩
x^2-a^2=(x+a)(x-a)
複二次式で四次篩
x^4-a^4=(x^2+a^2)(x^2-a^2)
同様に八次篩、十六次篩。。。
- 283 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 19:10:45.55 ]
- 以上桁は無意味
- 284 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 19:24:01.64 ]
- 私は世界の鍵を持っているbyスイーツ w
- 285 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 19:26:14.07 ]
- >>269
なるほど、そんなのあったなぁ
ビットフィールドでやってますた
- 286 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 19:30:49.59 ]
- あ、十六次篩、二百五十六次篩か
- 287 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 19:32:52.70 ]
- コード的にsqrtのネストなので
- 288 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 19:36:05.13 ]
- 指数は二倍ずつか
- 289 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 19:37:48.46 ]
- >>283
ある日突然道端のオヤジが公然わいせつオナニーを始めたところを想像してほしい
嫌だろ？
- 290 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 19:41:29.02 ]
- 勘違いを訂正
ちゃんと判定出来るよ
- 291 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 19:44:27.00 ]
- 2^n次篩だから桁は無意味だから
他の暗号方式を考えないとね
- 292 名前： ◆QZaw55cn4c mailto:sage [2012/05/06(日) 21:47:31.01 ]
- >>254
リンク先をいろいろ紹介していただいてはいるのですが、難しくて私には一生理解できないだろうと思います。
そこで申し訳ないのですが、巨大素数の原始根を求めるために素因数分解が必要となる道筋を、もしよろしければ教えていただけないでしょうか？
簡単に試行してはみたのですが、2^31 で丸一日かかる有様です。あと手を打つとすればマルチスレッド化でしょうが、手元のは屁ノムx6 だしなあ。
ideone.com/In1SB (java でごめんなさい）
なお全部の原始根を求める必要はなくて 300〜500位のものが数個手に入ればいいかと思います。
- 293 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 22:03:24.00 ]
- だからC/C＋＋じゃないならよそでやってくれと
- 294 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 22:06:14.59 ]
- 素因数分解ならn次篩使えば出来るよ
ソース見てわからなかったらゴメン
- 295 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/06(日) 22:11:25.74 ]
- 二次篩をネストしただけだから
- 296 名前：デフォルトの名無しさん mailto:sage [2012/05/06(日) 22:25:01.22 ]
- 2ch初心者も歓迎するスレです
- 297 名前：デフォルトの名無しさん [2012/05/06(日) 23:50:19.40 ]
- >>292
たとえばp-1= 7*11*13として3が原始根を確かめるには。(pは素数でないから例として良くないが)
ラグランジュの定理から、p-1の全ての約数x(p-1を除く)に対して、3^x ≠ 1 (mod p)であることをいえばよい。
具体的には、3^(7*11) ≠ 1 (mod p)、3^(11*13) ≠ 1 (mod p)、3^(7*13) ≠ 1 (mod p)でいい。
ラグランジュの定理 (群論) - Wikipedia
G を有限群とし、H を G の部分群とする。このとき、H の位数は、G の位数を割り切る。
- 298 名前：デフォルトの名無しさん [2012/05/06(日) 23:55:25.56 ]
- >>292
簡単に言えば、Z/pZの元 aのn乗が１となるのは、nはp-1の約数に限る。(ラグランジュの定理)
p-1以外では1とならなかったら原始根。
- 299 名前： ◆QZaw55cn4c mailto:sage [2012/05/07(月) 01:25:25.23 ]
- >>297
なるほど、定義どおりにいけば、n が p について原始根であるかどうかをみるのに、現状では
n^1, n^2, n^3, ... n^(p-2) について 1 (mod p) をみなければならない
ところが、教えていただいた方法では
p - 1 の約数についてのみ、と個数を絞り込むことができる
のですね。仮にメルセンヌ素数 2^1279 - 1を目標にすると、
2^1279 - 1 = 2(2^640 + 1)(2^320 + 1)(2^160 + 1) .... (2^5 + 1)(2^5 - 1)
まで因数分解できるので、個々の因数を素因数分解していくと、チェックしなければならない場合の数が激減しますね。少なくとも 2^1279 とおり、ということはないはず。
あとは何が原始根の候補となりうるのかが判別すればいいのですが、これは、>>292 でも使用しているのですが、計算量が増えるにしても 2 から順次チェックするのが絞り込みやすいのかもしれません。
しんどいですけれども。
- 300 名前： ◆QZaw55cn4c mailto:sage [2012/05/07(月) 01:26:49.83 ]
- >>299
×n^1, n^2, n^3, ... n^(p-2) について 1 (mod p) をみなければならない
○n^1, n^2, n^3, ... n^(p-2) について 1 (mod p) とならないことををみなければならない
- 301 名前：デフォルトの名無しさん [2012/05/07(月) 02:01:22.14 ]
- あと、原始根をすべて列挙するのに、素因数分解が使える。
あと原始根の簡易判定としてこれ。
奇素数 p を法とする原始根 g は p を法として平方非剰余である．
nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf
- 302 名前：デフォルトの名無しさん mailto:sage [2012/05/07(月) 04:50:17.14 ]
- >>285
話がまだ続いているから、こっちに移動してもうちょっと詳しく質問してよ。
画像処理 その13
toro.2ch.net/test/read.cgi/tech/1301896601/
582 名前：デフォルトの名無しさん [sage]： 2012/05/07(月) 01:09:44.70
>>579
処理系依存だがや
583 名前：デフォルトの名無しさん [sage]： 2012/05/07(月) 02:54:26.37
処理依存の回答を求めているからだろ。だからもっと依存の強いSIMDのようにハードリソースに合わせたソフトのつくりはアリだと思う
unsignd longは固定64bitと書いてあるように読みとれないか？処理系が変わると大元設計から変えるんだろうね。
えっと、、だがや
- 303 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/07(月) 05:41:05.67 ]
- n次篩使えば桁は無意味なのに
- 304 名前：デフォルトの名無しさん mailto:sage [2012/05/07(月) 06:08:21.84 ]
- いい加減篩廚は別スレ立ててやれや
- 305 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/07(月) 06:17:52.76 ]
- 四次篩
x^4-y^4=(x^2+y^2)(x+y)(x-y)
と分解したときにnの因数が()３つに分配されることを期待して
gcd(n,x+y)
からnの約数を見つける
同様に八次篩、十六次篩...ができる
- 306 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/07(月) 11:00:55.86 ]
- 冷静になって考えたら二次篩でも四次篩でも演算回数同じだった
- 307 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/07(月) 11:36:43.44 ]
- 二次篩で既にnによらない演算時間だった
>>292
二次篩でいいよ
n=3937
√3937≒63
63^2-n=32=2^5
64^2-n=159=3*53
65^2-n=288=2^5*3^2
(63*65)^2≡(2^5*3)^2(mod n)
gcd(n,63*65±2^5*3)=31
- 308 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/07(月) 11:47:16.92 ]
- これを実装したよ
- 309 名前：デフォルトの名無しさん [2012/05/07(月) 11:50:11.99 ]
- 速いソフトのバリナリあるから比較して味噌
Windows Factoring Software Binaries (64bit & 32bit)
gilchrist.ca/jeff/factoring/index.html
gilchrist.ca/jeff/factoring/benchmark.html
gilchrist.ca/jeff/factoring/pseudoprimes.html
- 310 名前：デフォルトの名無しさん [2012/05/07(月) 12:11:03.30 ]
- このソフトで12秒かかった素因数分解。
これより速くないと世界一は無理だな。
yafu-1.31
sourceforge.net/projects/yafu/files/1.31/yafu-1.31.zip/download
factor(222222222222222222222222222222222222222222222222222222222222222222222)
- 311 名前：デフォルトの名無しさん mailto:sage [2012/05/07(月) 12:18:46.29 ]
- いい加減にしろ
- 312 名前：NAS6 ◆n3AmnVhjwc mailto:sage [2012/05/07(月) 12:22:01.86 ]
- 二次篩だったから俺の考えてたより遅いよ
- 313 名前：デフォルトの名無しさん mailto:sage [2012/05/07(月) 15:28:37.39 ]
- >>302
そのスレのは私自身が書き込んだレスじゃないんですが・・・
だれか貼っつけた人が収拾してください
- 314 名前：デフォルトの名無しさん mailto:sage [2012/05/07(月) 19:19:13.94 ]
- 学が無くてもそれなりに語れるネタに狂喜乱舞て状況だな
- 315 名前：デフォルトの名無しさん mailto:sage [2012/05/07(月) 23:02:24.54 ]
- スレタイ100回読め
- 316 名前：デフォルトの名無しさん mailto:sage [2012/05/08(火) 19:43:04.58 ]
- 【韓国ＢＢＳ】台湾人は日本が好きで韓国を嫌う、その理由は？
韓国のコミュニティサイト「ガセンイドットコム」の掲示板に「台湾人たちが、日本が好きで韓国嫌いな理由は？」とのスレッドが立てられたところ、さまざまな意見が寄せられた。
スレ主は、台湾人は韓国と日本の好き嫌いがはっきり分かれていて、韓国は嫌いだが日本がとても好きだとの記事を紹介した。
スレッドには、その理由について「日本と台湾が島国同士だからではないか」との意見が数多く見られた。
・「台湾や日本は両国とも島国で、韓国を困らせるのが趣味。しかし台湾がいくら困らせてようとしても、韓国はあまりにも強くて賢くて倒れない」
・「島国どうしなので、傾向が似ているから惹かれあうのでは。どちらも内部の問題を外部のせいだとか方便を使う」
・「島国は島国どうし仲良くするのが好き」
・「私たちはできるなら台湾や日本の物を使わないことにしましょう。むしろヨーロッパやアメリカの製品を使用しましょう」
news.searchina.ne.jp/disp.cgi?y=2012&d=0508&f=national_0508_070.shtml
◆台湾が韓国嫌いな本当の理由はこれ
韓国は「我々は薄情な裏切り者の日本とは違うから台湾との国交は永遠に断絶しない」と言っておきながら
台湾に公用車として５万台の不人気韓国車を売りつけ、代金を受け取ると同時に、台湾と国交を断絶し中国との国交を結んだ。
しかも韓国の新聞やＴＶはこれを「韓国の大勝利」「慌てふためく台湾」と馬鹿にして煽り、
ソウルや釜山にあった中華街を様々な規制や嫌がらせで潰し台湾系華僑を追い出した。
その後も韓国は何十年も台湾を攻撃し続けた。
・韓国は、アジアスポーツ大会の主催国争いにおいて、「台湾が権利を譲らなければ大会から台湾を追放する」と恫喝した。
・韓国は、「台湾は国家ではないので参加させない」と国際会議などで台湾を閉め出すなどの行為をしてきた。
・韓国は、台湾が国連やIMFなど国際機関へ加盟することに反対した。
・韓国は、1997年にデフォルトしIMF管理下に入ると台湾に対して「両国間の国家改善のため」といって100億ドルの資金援助を要求した。
- 317 名前：デフォルトの名無しさん mailto:sage [2012/05/09(水) 06:42:43.87 ]
- >>316
C/C++以外のことも勉強になるな。
でも、スレチだろ。
- 318 名前：デフォルトの名無しさん [2012/05/10(木) 06:57:15.84 ]
- アルゴリズムを実装してるのですが、二分木のrightとかleftが大量に出てきて、
しかも同じ内容の箇所をright用とかleft用に書き直しなので、マクロとかで上手くかけないかと思ってます。
func1() {
tree->left = tree->right;
tree->left->left = tree->right->right;
}
func2() {
tree->right = tree->left;
tree->right->right = tree->left->left;
}
たとえば上記のような2つの処理を書かないと駄目なとき、
funcX(A,B) {
tree->A = tree->B;
tree->A->B = tree->B->B;
}
と書いて
funcX(right,left);
funcX(left,right);
とかやりたいのですが、やり方はないでしょうか。元のtreeのメンバを配列にするのは
できないです。
- 319 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 07:57:24.58 ]
- treeにl()とr()を実装
- 320 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 07:58:13.70 ]
- treeの構造も書かずに聞くかよ。
例えばこんな手はあるぞ。
struct tree {
type * data;
struct tree * left;
struct tree * right;
};
↓
struct tree {
type * data;
struct tree * sides[2];
};
enum {Left, Right};
これなら、
funcX(int a1, int a2)
{
tree->sides[a1] = tree->sides[a2];
}
みたいに書いて
funcX(Right, Left);
みたいに書けるぞ。
- 321 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 08:16:07.85 ]
- 質問の意図や前提をくみ取れない糞質問
が多い。それで回答者が逆質問をしたり
悪口を言ったりする。それを前もって思
い描く力が絶望的に欠如してるに違いない。
スーパーハッカーだけが意図を理解できる。
レアなそういう神が颯爽と登場する予感。
- 322 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 08:29:50.72 ]
- なんだろうね、少し前にもあった、この奇妙な改行感は。
行の短さも考慮すると、
コードが大量に出てくるこの板を、携帯で読んでるのかね。
バカじゃないの。
- 323 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 08:33:41.35 ]
- >>322 どこを縦読み？
- 324 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 08:34:47.70 ]
- 少なくともtreeの構造は必要だな
- 325 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 08:52:53.61 ]
- ＞質 問の意図や前提をくみ取れない糞質問
＞が 多い。それで回答者が逆質問をしたり
＞悪 口を言ったりする。それを前もって思
＞い 描く力が絶望的に欠如してるに違いない。
＞ス ーパーハッカーだけが意図を理解できる。
＞レ アなそういう神が颯爽と登場する予感。
- 326 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 08:54:21.11 ]
- こんなのとか
template <bool Swap>
struct LR {
Tree* operator()(Tree* parent) {
return Swap ? parent->right : parent->left;
}
};
template <bool Swap>
void funcX() {
LR<Swap> Left;
LR<!Swap> Right;
Left(tree) = Right(tree);
Left(Left(tree)) = Right(Right(tree));
}
メンバ変数ポインタを使ってみたりとか
template <bool Swap>
void funcX()
Tree* Tree::*left = Swap ? &Tree::right : &Tree::left;
Tree* Tree::*right = Swap ? &Tree::left : &Tree::right;
tree->*left = tree->*right;
tree->*left->*left = tree->*right->*right;
}
- 327 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 09:05:47.43 ]
- 上のoperator()は&が抜けてた。正しくはこうね Tree*& operator()(Tree* parent) {
下は書き間違いが起こりやすそう、最適化が効きにくそうで微妙かも。
- 328 名前：デフォルトの名無しさん [2012/05/10(木) 11:17:15.73 ]
- Treeの構造はこんな感じです。(本当はもっと名前が複雑で長い)
class Tree {Tree* right; Tree* left;}
bool使ったTemplateは複雑な条件に対応できにくそうで、配列はメンバを書き換えないと駄目なのでむりです。
そこでdo {}while(0)のマクロを使って
#define macro1(right, left) do { \
t-> ##right = s-> ##left; \
} while (0)
とかで書きました。
- 329 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 11:47:52.24 ]
- >>328 その ## 連結は不要で不正。
- 330 名前：デフォルトの名無しさん mailto:sage [2012/05/10(木) 11:56:48.21 ]
- >>318
codepad.org/pMp2PuSI
- 331 名前：デフォルトの名無しさん [2012/05/11(金) 01:59:16.78 ]
- テンプレートでかけるとは。
すごい
- 332 名前：デフォルトの名無しさん [2012/05/11(金) 02:26:59.71 ]
- 「テンプレートでかけるとは。 」
と思うほうが、すごい
- 333 名前：デフォルトの名無しさん mailto:sage [2012/05/11(金) 06:15:16.11 ]
- うん
- 334 名前：デフォルトの名無しさん [2012/05/11(金) 06:27:13.96 ]
- テンプレートでポインタとか使えるとか知りませんでした。
- 335 名前：デフォルトの名無しさん mailto:sage [2012/05/11(金) 06:58:09.41 ]
- テンプレートがどこに出かけるの？
- 336 名前：デフォルトの名無しさん mailto:sage [2012/05/11(金) 07:42:00.96 ]
- スムーズに動く2Dアクションを作ろうと思うんですが、マップってある程度(8ドットくらい？)ブロック単位で配列を置くだけでいいんでしょうか？
その場合、マップが広いとやたら長くなりそうなんですが…
- 337 名前：デフォルトの名無しさん [2012/05/11(金) 15:12:33.62 ]
- C++はなんでも作れるって先輩から聞いていたんですが
入社４年でなんとか、使えるようにはなったんですが
未だに彼女が作れません。
本当に作れるんですかね？
|
 |
