2008-03-01から1ヶ月間の記事一覧
http://b.hatena.ne.jp/entry/http://d.hatena.ne.jp/lovelovedog/20080403/gizi はてな観察部 (はてなを観察する) におきましては, そもそも削除申請されるのか? その場合に削除申請が通るのか? という点に注目です.
まだalpha版らしい. 個人のブックマークも出来るらしい. 情報系としてはありがたい.
AND, OR, NOTからなるn入力1出力サイズsの回路の数の上限は, 2^s (2+2n+s)^s2^s (2+2n+s)^{2s}. 素子の数をk, ファンインの数を高々mにして同様の上限を考えると, k^s (2+2n+s)^sk^s (2+2n+s)^{ms}.
PQCrypto 2006の2回目をやるようだ. 詳しくはPQCrypto 2008 - The Second international Workshop on Post-Quantum Cryptographyを参照のこと. 今度はLNCSで本が出るそうな. 格子関係だとSilvermanとSzydloでNTRU寄りのようだ. 前回はRegevやらNguyenやら居…
参考:Gregory Neven's Home Page - An edited volume of IOS Press Cryptology and Information Security Series on Identity-Based Cryptography. IACRのカレンダーを見ていて気付いた. 納得の面子. どこかが邦訳に動いていることに期待.
(Z[x]/<(x^n-1)/(x-1)>)^m (n=257, m=64) 上の内積を64回取るのに1秒くらい掛ってる. まぁいいんですけどね, 鍵作るのは1分位かけても問題無いから.
Rosen and Segevで書き忘れてた。DCRAからIND-CCA PKE w/o ROはCramer-Shoupがそう。
暫く機能停止らしい. やっとx>y>z>0が等差数列でx^2-y^2-z^2=n (Prob 135, 136) が分かったというのに.
Cryptology ePrint Archive: Report 2008/134 - A. Rosen and G. Segev “Efficient Lossy Trapdoor Functions based on the Composite Residuosity Assumption”Peikert and Waters (STOC '08, Cryptology ePrint Archive: Report 2007/279)で新しく提唱され…
Problem 157は面白かった. アルゴリズムを改良するとまだまだ縮みそうではあるが本業の方をいい加減やらないといけないので改良は止めておく. gosh> ;(time (apply + (map (lambda (n) (length (solve n))) (iota 9 1)))) ; real 38.250 ; user 37.843 ; sys…
暗号の安全性は一種の学習不可能性だよという話を先生からよく聞くのだが, 学習不可能性を暗号の安全性から示したのって, 格子系以外だと何かあったっけかな. 暗号→学習不可能性の話はECCC 2005辺りに載ってる筈. 逆はHBプロトコルの安全性やRegev05とかがそ…
108と110. 1/x + 1/y = 1/n で, 0 < x <= yという整数解の個数に関する問題. 解の構造は分かった. ぱっと思いつく方法だと1分ルールに反するので, 逆を考えるべきなのだろう. そういう方針であれば110の方も何とかなるのかな. 多分.またRioさんに離された. …
127問. Repunit系は129だけ残ってしまった. 位数を求めるのは面倒臭いなぁ. PROB119はこっちの方向が良いんだな. num->digitsは各桁にばらす関数 (use srfi-42) (list-ref (sort (list-ec (: b 2 1000) (: e 1 50) (if (and (> (expt b e) 10) (= b (apply +…
総合大会中に多少解いてたらしい. ようやく122問. Problem 26 面倒臭がって残していただけ. Problem 93 0除算? +inf.0になるからGaucheだと大丈夫. Problem 164 数え上げ. 漸化式を立ててメモ化で終了.
Cryptology ePrint Archive: Report 2008/119 - B. Chevallier-Mames, D. Naccache, and J. Stern, “Linear Bandwidth Naccache-Stern Encryption”を流し読み. Naccache-Stern knapsack cryptosystem - Wikipedia, the free encyclopediaか. 英語版だと記事…
何を思ったか20日に帰ることになっている. 領収書はどこで手に入るんだ?
404 Blog Not Found:アルゴリズム - 合コンの効用を最大化する 安定結婚問題が取上げられているので情報の添加.Iwama, K., Manlove, D. F., Miyazaki, S. and Morita, Y. “Stable Marriage with Incomplete Lists and Ties” (ICALP 99) によれば, リストに異…
理系のための口頭発表術 - 4403 is writtenでお薦めされていた本が生協にあったので買って読んでみた. 理系のための口頭発表術―聴衆を魅了する20の原則 (ブルーバックス)作者: R.H.R.アンホルト,鈴木炎,I.S.リー出版社/メーカー: 講談社発売日: 2008/01/22メ…
SCISのプログラムを適当にテキスト変換してアップした. ところで, F2mは, F_{2^m}なのかF_2^mなのか分かんないのでどうにかして欲しい. 2004以降のも適当にテキスト形式でアップすると思いますよ. 以下であってたorz ところで, SCIS 2003 15D-4↓が文字化けし…
slib - Mathematical Packages 何でMiller-RabinじゃなくってSolovay-Strassenなんだろう? 計算量的に特してるところあったかな?
112問. 数え上げに関する問題を解いた. 113, 114, 115とか.
scis.jpの設定を直した. とりあえず過去の公式サイトへのリンクだけ作っておいた. 専門委員会からの連絡はまだ無い様子.
久しぶりにCDを買った. Steal This Albumアーティスト: System Of A Down出版社/メーカー: Columbia発売日: 2010/08/24メディア: CD クリック: 11回この商品を含むブログ (5件) を見る Untitledアーティスト: 54-71出版社/メーカー: LASTRUM発売日: 2002/07/…
そういえばあと2週間もすれば学部ゼミ. 今年はKatz and Lindellらしい. Introduction to Modern Cryptography: Principles and Protocols (Chapman & Hall/CRC Cryptography and Network Security Series)作者: Jonathan Katz,Yehuda Lindell出版社/メーカー…
プレゼン資料直した. NTLをちょっと弄ったところで満足した. これから多項式の掛け算とかばりばりしなきゃいけないんだが, 前回のテストではZZ_pX型の多項式とZZX型の多項式の掛け算をしようとするとエラーになった気がする. 型のキャストが必要だった覚えが…
Problem 94 L-L-(L+1)またはL-L-(L-1)の三角形で面積が整数になるものを探索. 思いついてからも計算ミスで詰まってた. Problem 98 試行錯誤で解いた. 全然面白くない. Problem 100 分かれば簡単. Problem 111 cartesian-productとcombinationsのおかげで大分…
(fold + 0 '(2 2)) ;-> 4 (use srfi-43) (vector-fold + 0 '#(2 2)) ;-> 5 (vector-fold + 0 '#(2 2 2)) ;-> 9 (vector-fold + 0 '#(2 2 2 2)) ;-> 14 (vector-fold + 0 '#(2 2 2 2 2)) ;-> 20 (vector-fold + 0 '#(0 0)) ;-> 1 (vector-fold + 0 '#(0 0 0))…
やっとこさ98問100問. Problem 72 手元の計算結果では一番高速なものでgauche, Pen 4 3GHzで2.781s. Problem 79 手計算の方が速い. Problem 80 SICPで課題問題だったと思うんだが. 普通にdecimalクラスを作って例の方法で近似. 2乗根の場合は古くから使われ…
以下を示せば12月時点からの改善になっているらしい.任意のと原点を通るk次元超平面Pについて, のPに対する垂直成分を考える. このとき, が任意ので成立する.これで近似度を大体√nくらい削れる. 反例の構成: 右下方向への射影でノルムが増えている.
I. Dinur, E. Grigorescu, S. Kopparty, and M. Sudan “Decodability of Group Homomorphisms beyond the Johnson Bound” 概要を読む限りではHadamard符号を抽象化したもののリスト復号ぽい. Goldreich-LevinやKushilevitz-Mansour, Akavia-Goldwasser-Safra…
