Introduction to Identity-Based Encryption (Information Security and Privacy Series)作者: Luther Martin出版社/メーカー: Artech House発売日: 2008/01メディア: ハードカバー クリック: 14回この商品を含むブログを見る VoltageのLuther Martinが書い…

すっきりと解決したのでメモ. {-1,0,+1}要素のランダムなn次元ベクトル (c_0,...,c_{n-1}) を考えて対応する巡回行列を確率変数としてP_nとおく. l_2-ノルムに対応する作用素ノルムの上限は固有値の絶対値の上限に等しい. (n次正方行列を考えるので.) 巡回行…

とはいえ多項式時間じゃなくって, 指数時間掛かる方ですけどね.Ajtai, Kumar, Sivakumar (STOC 2001) を真面目に解析したら時間計算量2^{5.9n}, 空間計算量2^{2.95n}だったよとNguyen and Vidickが報告したのが今年の話 (J. Math. Crypt. 2009). Voulgaris a…

誰の役に立つのか分からないけど. 分岐が意外と多い. Jacobi記号はLegendre記号の一般化になっているので, Legendre記号もこれで求められますよ. (define (Jacobi a n) (cond ((= a 0) 0) ((= a -1) (cond ((= (modulo n 4) 1) 1) ((= (modulo n 4) 3) -1)))…

8月5日はハーコーということでハードコアの日だそうです. (ちゃんと日本記念日協会に届け出たそうで.)ということなのでハードコア関数の話をします. Goldreich-Levinハードコア述語とリスト復号の話はよく出るんですが, GLハードコア述語とフーリエ変換の話…

とりあえず10個かー. 授業で証明読んだもの 停止問題とそのヴァリアント ビジービーバー ライスの定理 L(PDA)?={0,1}^*, L(PDA1)?=L(PDA2) PCP (Postの方) 証明知らないもの ヒルベルトの第10問題 ワンのタイル 読みたいもの DBLPから見繕う. 群同型 en.wiki…