RSAでm^e mod n = mとなるmの個数を最小化するeの総和を求める問題. 暗号屋としては解かねばなるまい. 数論系の暗号は久しぶりなのでちょっと迷ったが, 一応解いた.

70問( ´ー｀) 801-900に入った. 条件付き最短パス探索問題 (Problem 81とProblem 82) は面白いな. n次正方行列について, Problem 81は計算回数がO(n^2)のアルゴリズムか. Problem 82はO(n^3)のしか思い浮かばなくて80s位掛かる. もう少し練るべきか. 条件の…

A remark on primality testing and the binary expansion « What’s new 論文の方を読む気はしないが面白い結果だなー. 十分大きなnについてnビットの素数pが存在し, i=0,...,n-1についてp \pm 2^iは全て合成数. 決定的な素数判定では全ビット読む必要があり…

Problem 69 騙された(;´Д｀) 気付くまでに20分掛るのは暗号屋としてどうかと思う. 62問になったので上手くいけばTOP 1000入り.

Qi Cheng and Daqing Wan “On the List and Bounded Distance Decodability of the Reed-Solomon Codes.” (FOCS 2004, SIAM J. Comp. 37). RS符号のリスト復号アルゴリズム (Guruswami-Sudan) の限界を超えた場合, リスト復号またはBDDが出来るかという問題…

60問ヽ( ´ー｀)ノ もうちょっと頑張ればTOP 1000か. 動的計画法を知らなくても陸プログラマでも何とかなるものだ. Problem 169とか普通の再帰+メモ化で何とかしたしな. それで出来るように丁度良く問題が作ってあるんだねと納得.

Guruswami and Vardy “Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard” (SODA 2005). MLDは最尤復号でいいんだったかな. MLD-LinearとはF_q要素のm×n行列とシンドロームsと正整数wを入力として, Hv^t=s^tかつハミング重みがw以下となるn次の…

ようやく51問. Problem 183はそこそこ簡単だった. 先に手を動かすのが大事なのか.

Problem 59は暗号文の解読なのだが鍵が3文字で暗号文が1201文字なので, 頻度解析を行えば手でも出来る気がしてきた. XORがちょい面倒っていうくらいか.

2/9を終えたところ. nが341550071728321未満のときまでは素数判定がO(log^3 n)か. Miller-Rabinテストはやっぱり偉いんだなー. ところで本業の方をschemeで書くという暴挙はどうだろう. LLLとか実装すんの. 大変そう. ;Refs:http://www.ice.nuie.nagoya-u.ac…

読まずに語るがエア批評, レムの『虚数』は何と呼ぶ. (七五調) ref:エア感想・エア批評 - ARTIFACT@ハテナ系

やっとこさ30問. 全体で182問なので, 先は長いなぁ( ´ー｀) CかC++かDの練習をする心算だったのに何故かgaucheで解いている.

解けるものからガシガシと. プログラムの練習がてら, 目標を70問としてやることにする. 100万までの素数表を作るのが面倒なので(define PRIMES (list ...))とxyzzyのscheme-modeからgaucheに喰わせようとしたら落ちた.

アルゴリズム大募集! C&R研究所 - コンテンツ募集 2008年前半とあるのであと4ヶ月か. アレから音沙汰無いね. RS符号のエラー訂正アルゴリズムであるところのBerlekamp-Masseyとか入れとけば良かった.メモ:松本眞:互除法. 面白そうなので後で読む.

カメラ発見 段ボールの画像を発見したので後で差し替えること 半年前の写真まであるじゃないか 卒論発表1日目 理論系だけ聞いた 先生の部屋を片付ける 何でこんなに紙が多いんすかorz RS符号のList-Decodingの話とDLを絡めた論文を発見. 後で読む 某所用の予…

Regev05やらGPVの公開鍵サイズをm=5nlog n, q=O(n^3)で見積もってみた. 大体n=512のときに鍵サイズが256Mbから1Gbか. Ajtai-Dworkのn=32のときにn^5 log nで160Mbとかにに比べればかなりの改善ということが分かる. 定数項が結構利いてくるものだ. 現実的には…

CCC 2008 Accepted Papers 量子と多証明者対話証明が多い. 符号周りは読むことにする.

emacsとかそっち系のテキストエディタもFirefoxみたいに拡張というかアドオンで設定できるようになると良いんじゃないか説.

Papers accepted to STOC 2008 偽らざるもの : STOC 2008 accepted papers例年STOCの論文はろくすっぽ読んでないわけですが, 最近の加法的組合せ論からくる結果はかなり大きいのだなぁというのが感想. Naorのはタイトルが気になるので後で読もう. Reed-Mulle…