D10で見つけたバグが直ってないや.

方針が間違っているので後で直さないといけないが, とりあえずハッシュの方が相当速いことが分かったのでメモ. a2の方が冗長なアルゴリズムだが, それでもa2の方が速い. n=18くらいまでは簡単にいける. (use gauche.collection) (define (a1 n) (define (f l…

my choices [Oded Goldreich] RSSが配信されているのでそっちで読んだ方が見易いかもしれません. 理想としてはWordpressに移行してTeXプラグインを入れて書いてほしい. TrevisanやTaoみたいに.

ようやく解けた. 現段階だと10分掛かってるのでもっと短くしよう.

概要 Koichiro Noro and Kunikatsu Kobayashi. “Knapsack Cryptosystem on Elliptic Curves.” (ePrint 2009/091)を軽く読んだ. 書き直してみたら拡張ElGamal暗号の改悪になってしまった. したがってこの論文の価値が消滅した. 面倒くさいので正しい構成は元…

コンピュータ代数ハンドブック作者: J.フォンツァガテン,J.ゲルハルト,山本慎,三好重明,原正雄,谷聖一,衛藤和文出版社/メーカー: 朝倉書店発売日: 2006/06メディア: 単行本 クリック: 28回この商品を含むブログ (2件) を見る Modern Computer Algebra作者: J…

ブックマークでやれと思った. Mihir Bellare and Thomas Ristenpart. “Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters" IBE Scheme.” (ePrint 2009/084, EUROCRYPT 2009) Brett Hemenway and Rafail…

Problem70だかProblem72だかで使ったものを再利用して解いた. n=2〜4,000,000のphi(n)を求めるだけで60秒掛かっているのが難点か. もっと速くなる気もする.

なんで前回解けなかったのか分からない. 富豪的にgroup-collectionを活用しても, 0.072秒. Pen4からCore2Quadに変えた所為もありそうだが.

ダメ論文に攻撃成功。何故かMS Wordで書かれた論文は攻撃しやすい。

久し振りにProject Eulerを解く. 最近追加された中で一番楽そうだったものを選択. 某アルゴリズムを使わなくても13秒. 使うと3秒であった.

Paillier暗号 - Wikipedia 英語から訳した. 後は詳しい人にお任せ.英語版の方だと岡本―内山暗号 (en:Okamoto-Uchiyama cryptosystem)やDamgård-Jurik暗号(en:Damgaard-Jurik cryptosystem)もある. Chor-RivestとOTUくらいは日本語版作るかね.

論文書き終了. 共著になった上, 向こうが殆ど編集してくれたので楽だった. まぁ5時まで起きてましたけど. 代数体の整数環に触れてしまった. そうそう使う機会も学ぶ機会も無いだろうと思っていたのだが. そんなところに行きたくはないんだが, 行かざるを得な…

証明を書いて最後に辻褄が合うようにパラメータの計算をしていてえらい変なことになっている. 調べてみると先方の写し間違いだった. 元論文を探して修正したところ計算が合ったのでよしとする.

既存の論文（主要な著者は4-5人程度) だと記号の使い方が引き継がれているのだが, 場合によって新しく記号をつけ直したりすると読み辛くてしょうがない. 数学系から格子に入ると横ベクトル主体で書く. 2000年以降の暗号から入ると縦. 符号も元々横ベクトルで…

IEEE Symposium on Security and Privacy - Accepted Papers (via: topics I like: Accepted Papers IEEE Symposium on Security and Privacy)

2^{2n}回のZ_q上の操作または集合演算を, qn^2回の実数演算に落とせた. フーリエ変換は偉大である. これでn=1024でもテストできるようになった. 今までn=8でしか出来てなかったことに比べれば進歩だな. (nが大きければ大きい分だけ桁落ちが起きそうで, それ…

STOC 2009 - Accepted Papers (with Abstracts) 格子暗号は2件. Peikertだけかと思ったら, Gentryが凄いの出してきた. イデアル格子ベースの暗号でNC1の回路をシミュレートできるらしい. エラーが足されるせいで, O(log n)までなのかな. エラーを外せれば任…

面倒臭くってリンクする気が起きない. 非ゼロの整数に関しては素因数分解した結果の指数の列を無限次元ベクトルと考えると一意性が楽に示せますねと思いました. を 2^{Z^+}みたいに考えるというのが数学的には単純で宜しいと. 1は(0,0,...)と対応して良いと.…