偽らざるもの : STOC 2008 速報のマネ.Nguyenも通したらしい. “Finding Short Lattice Vectors Within Mordell's Inequality” (STOC '08) Mordell's inequalityってのはエルミート定数に関するあれだよな. って奴. CRYPTO 2006の論文の続きだと思うのだが, …

続き. 少し考えて計算可能性を示す案を思いついた. そもそもの野田さんの疑問 *1とは違うと思う上に面白く無い. まぁいいや, 書こう.先ほどと同様に可逆圧縮アルゴリズム全体の集合をCompとする. ただし今回はとしてComp^+:={(M_C,M_D)|M_C,M_D:TM. 全てのx∈…

ふと抱いた疑問：連長（ランレングス）圧縮はランダムな入力に弱く，ランダムな入力に対しては出力の方が長くなりがちなことは有名．このことを一般化し... 任意の圧縮アルゴリズムに対して，出力が入力より長くなるような入力は構成できるか？ 「任意の」と…

思い出すたびに内容が増えます 探索版で問題を定義しているのに問題はNP完全問題とあるプレゼンが二, 三件. (どなたの資料だったかは覚えていない.) H2NP WEB 出版のCRYPTOnnnnカンファレンス レポート. 一度読んだ覚えがある. 読み返してみると各所に勘違い…

[語源]なぜ東京工業大学（Tokyo Institute of Technology）の英語での略称はT.I.T ではないのか？ - 捨身成仁日記 炎と激情の豆知識ブログ！ TUT - odz buffer 今でもドメインはtitechですが, 正式な略称はTokyo Techです. ご注意を. 本学の略称 本学では，…

笑いの神様、ありがとうございました。

On-the-fly (Girault, Poupard, Stern) で知識が漏れやすい場合ってあるじゃないですか. そういうときは証明者が何も送らなければいいんじゃないか? という発想が元だと思う.秘密鍵はm次元バイナリベクトルx. 公開鍵は格子ハッシュのインデックスであるZq要…

d:id:tri_iroに書いてある話を読んでいた. BBは (俺の中で) 計算不可能な関数の例でしかなかったので, 色々と蒙を啓かれた. DFAを検査と言ったときには二通りの解釈が出来る DFAの出力だけをメモできる DFAの内部の状態遷移を見てメモできる 例の問題は後者…

投稿した. #5389. 自動で印字しようと思ったが, さて1秒待つとかどう書くのかと悩み, 結局ユーザーの入力に任せた. 盤面を引数に取りながら更新するのでPLT Schemeのdraw.ssとか使うとアニメーションも出来るなぁと今更思った.

しまった. nを素数にするとFFTが使えない. となると, 計算量はO(n^2 log^c n)か. メリットが消えてしまうな. 直そう. 直ったかと思ったがダメぽい? n=2^kとして, x^n+1はZ上既約. また2nがq-1を割り切らないとき, Zq上でも既約かと思ったがそうではない. 根…

ref:わたしが知らないスゴ本は、きっとあなたが読んでいる: 数学ぎらいは幸せになれないか? 「生き抜くための数学入門」のコメント欄.簡便のため, Nは0を含むとする. 数学的な記法で表すと以下になる. 証明 任意の自然数について, であることは明らか. 以下,…

K. Bentahr, P. Farshim, J. Malone-Lee, N.P. Smart. “Generic Constructions fo Identity-Based and Certificateless KEMs” (Cryptology ePrint Archive: Report 2005/058) に載っているという話なので読んだ. 7章でOW-ID-CPA IBEとROを用いたIBKEMの構成…

IND-ID-CPAなIBEも出来たぽいヽ( ´ー｀)ノ 仮定が強いが, そこは勘弁.

Formal Methodってどんなんだろうね, と思ってDolev-Yaoを眺めてみた. 完全に安全な暗号系を最初に仮定するところが気になるが, まぁ, そういうものが存在するとして, 安全なプロトコルは可能か? という話らしい. Man-in-the-Middleを如何にして防ぐかという…

1/10がKnuth先生の誕生日らしく各所で祝辞が述べられている. 70歳だそうな.References. Shtetl-Optimized » Blog Archive » Volume 4 is already written (in our hearts) The Geomblog: Happy Birthday, Don Knuth ! in theory: Don Knuth is 70 11011110: …

Y.-D. Zhao and W.-F. Qi “Small Private-Exponent Attack on RSA with Primes Sharing Bits.” (ISC 2007) ISC 2007 - Programに発表資料があるので見てた.N=pqとして, pまたはqの半分のビットが既知の場合 d

▼ 「計算的な深さと脳」 で書いた計算的深さの概念はシンプルかつ重要だと思う。 もしそうならこの程度の概念がすでに専門の学者によって発明されていないはずはない。そう思ったのだけど、相変わらず私のアンテナにはかかってこない。もしかしたらまだ存在…

そんなに大きい整数を相手にする気も無いのだが. 2^{20000}辺りを引数にすると差が出た. ;(define (nu_2 a) ; (cond [(zero? a) "infty"] ; [else (the number of consecutive zeros inthe LSBs of the binary representation of a)])) (define (nu-div a) (…