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…

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

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

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

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

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

第3回折り紙の科学・数学・教育 研究集会 12/16日に白山で. 聴きに行こうかな (計算機幾何は初心者だけど).

昨日日経新聞に出てた. J. Schaeffer, N. Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, S. Sutphen. "Checkers Is Solved " -- Science 最善手を打ち続けると両者引き分け. 1989年から回し続けてたらしい. 概要を読むと引き分けと書いて…

2007/07/01 改稿. NP問題の定義を追加. 家で勉強してた. 符号のリスト復号に詳しくなった. 矢沢久雄の情報工学“再”入門 第1回 アルゴリズムと計算量---「計算量理論」を理解し，アルゴリズムを評価するという記事を見て, 後半がダメダメなので突っ込み. なん…

杜撰な研究者の日記: ISIT 2007 のプログラムで格子セッションが取り上げられているのでメモ. 以下, メモというか覚書. 符号の文脈で格子が使われているのを数本見たけど, E_8格子の最適性の議論とかでげっそりした覚えがある. 大体CVPを解くという問題設定.…

線形合同法で生成された乱数が全て見られる場合, と4つ見ると以下の式が立てられる. ここからa, b, mが推測出来るんじゃないかと思ったが, どうだろう. これは解けるのか?

http://pc11.2ch.net/test/read.cgi/tech/1177988460/122を見てちゃんと手を動かしてみた. 3+5 +++>+++++< [->>+>+<<<]>>>[-<<<+>>>]<<[->+>+<<]>>[-<<+>>]<<<各ループでこう動いている. A B 0 0 0 B A A A B A 0 A 0 A+B B A B A+B 0あと内容を破壊しない引…

あとでチェックする. 格子関係は無しか. あるじゃねーか(;´Д｀) Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima Johannes Blömer and Stefanie Naewe In this paper we introduce a new lattice problem, the subspace avoi…

Papers accepted for presentation in STOC 2007 分かるものにはリンクを張っておく. 暗号 Iftach Haitner and Omer Reingold. Statistically-Hiding Commitment from Any One-Way Function (Cryptology ePrint Archive 2006/436) Dmitry Gavinsky, Julia Ke…

質問から2つ. エクセルで擬似正規乱数を、RAND()+RAND()+RAND()+RAND()+RAND()+RAND()+RAND()+RAND()+RAND()+RAND()+RAND()+RAND()-6 で計算したところ、異常に頻発してマイナス値がでてこまっています。この式は各所で簡易で最適な擬似正規乱数を出力する手…

http://www.hyuki.com/d/200510.html#i20051020190000 以下、サイズをsとする。 正しいシャッフルは長さsの置換全体（対称群）からランダムに選ばなければならない。 void shuffle(int music[], int size) { int i; for (i = 0; i < size; i++) { int r = ra…

http://d.hatena.ne.jp/smoking186/20051003/1128346370 ちゃんと読んだら酷かった。 学校で作者三人の履歴を調べたら、暗号も計算論もやってなかった。そういうことか。生暖かく見守ろうということに。

Cryptology ePrint Archive 2005/347から。最近流行のPairing使ってKnapsack作ってみようぜという話の様子。 CKDH⇔Subset-Sumはbiliner mapを使うとほぼ自明。CKDHが解けるならSubset-Sumが解けるは自明でいいんだが逆を証明してないよ、これ。拡張CKDH*1解…

タイトル訂正。 一応計算してみよう。 Hotwired 完全にランダムなシャッフル再生は可能か(上) Hotwired 完全にランダムなシャッフル再生は可能か(下) n曲中、Aというバンドの曲がk曲ある。このn曲にそれぞれ1〜nの番号を付けて順に並べる。番号の付け方は真…

ボックスミューラー法の凄さを実感してみようの回。 いや、何となく書いたので。 Math::Random::MTが遅いので差が付く様子。乱数生成に時間がかからない場合(標準のrandとか)、算術平均の方が速かったりするようで。 あと算術平均の方を間違ってたので修正。…

大雑把に纏めるとこんな感じ。 名前 格子の種類 安全性 One-way function? 応用 NTRU NTRU-Lattice 証明なし NTRUCrypt(暗号) NTRUSign(署名) Ajtai-Dwork unique-Lattice (SVP) w/a A-D Cryptosystem PRG GGH Lattice (CVP) なし GGH-Cryptosystem 覚えてい…

英語を読むことを厭わないならそれは非常に便利なツール。本を串刺し検索出来るってのはすごいな。しかも検索語はちゃんと色付。 Google Print: Mental Poker -Magic Google Print: Traveling Salesman Problem ちょこちょこ定義とかを拾い読みするには大丈…

普通の無向グラフをひっくり返すとハイパーグラフになることに気付く。頂点を辺に、辺を頂点に。今更。

あー、確かに「DH問題が解ける⇔ElGamal暗号が解読できる」。