MarriageTheoremのこと

_ （6/2記：某勉強会。とても盛況で何より。その席上、某氏から以前の私たちの結果についての問い合わせを受けたのだけど、やっぱり何度説明してもあの結果は直観的に説明し辛いなぁと改めて感じた。）

_ （6/3記：自宅に籠って論文修正に集中できるのは休日の利点の一つである。）

_ 今日、Twitterで「○○幾何」という形の数学の分野名を列挙して遊んでいる人たちを見掛けて、それでふと思ったのだけど、「○○幾何」という順番に名前が繋がった分野名は多数あるのに「幾何○○」という順番の分野名はあまり見掛けない気がする。代数と解析と幾何の三本柱から二つ選んで分野名を作るときも「代数解析」「代数幾何」「解析幾何」の並びで、綺麗に「代数→解析→幾何」という順序に固定されているし、この辺りの分野名に関する感覚の背後には何が潜んでいるのだろう。

_ プレプリント確認状況：arXiv:math 2月23日分まで、IACR ePrint 2012/314まで

_ 気になった論文：A mathematical problem for security analysis of hash functions and pseudorandom generators（Koji Nuida and Takuro Abe and Shizuo Kaji and Toshiaki Maeno and Yasuhide Numata, IACR ePrint 2012/310）

In this paper, we specify a class of mathematical problems, which we refer to as ``Function Density Problems'' (FDPs, in short), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure pseudorandom generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Our argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. We also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints. Finally, we discuss possible directions of future research on other cryptographic applications of FDPs and on mathematical studies on FDPs themselves.

（ステマ）

_ 気になった論文："Two grumpy giants and a baby"（Daniel J. Bernstein and Tanja Lange, IACR ePrint 2012/294）

Pollard's rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups. This paper presents two reasons that Pollard's rho algorithm is farther from optimality than generally believed. First, ``higher-degree local anti-collisions'' make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic. Second, even a truly random walk is suboptimal, because it suffers from ``global anti-collisions'' that can at least partially be avoided. For example, after (1.5+o(1))\sqrt(l) additions in a group of order l (without fast negation), the baby-step-giant-step method has probability 0.5625+o(1) of finding a uniform random discrete logarithm; a truly random walk would have probability 0.6753\ldots+o(1); and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1).

当初はタイトルだけ見ていてBaby-Step-Giant-Step法の話だったとは気付いていなかったのだが、Twitterでこのプレプリントの話題が流れてきたので気付くことができた。

_ プレプリント確認状況：arXiv:math 2月23日分まで、IACR ePrint 2012/319まで

「第二回関西すうがく徒のつどい」というイベントがありますのでご紹介しておきます。公式サイト（？）より内容紹介を引用しておきます。（ちなみに「すうがく徒」というのは、「必ずしも数学専攻や数学のプロというわけではないけれども数学に興味関心のある人」を幅広く包含する造語のようです。）発表しなくても参加可能（というか、参加希望者が多すぎて希望者全員が発表できない可能性大）ですので、ご興味のある方は是非どうぞ。

関西のすうがく徒が集まりワイワイガヤガヤするイベントです。
前回は関東から九州まで高校生から社会人、現役の数学研究者まで、 分野を問わず、数学科はもとより医学部や文学部の方まで参加して頂きました。
数学好きの皆様の参加をお待ちしてます。

【参加資格】数学が好き

【発表】発表内容は数学,論理学,数理哲学,数学史,数理経済など数学や数理科学に関わることならなんでもおｋ

（中略）

【開催日時】9月8,9日.両日とも11時頃～18時頃

（中略）

場所
大阪大学豊中キャンパス

_ （6/12記：とある方の発表練習で面白い話を聴いて勉強になった。）

_ （6/12記：休日。へばっていた。）

_ （6/12記：休日。かなりたくさん買い物をした気がする。）

_ （6/12記：この頃は身体の冷えを防ぐために極力温かい飲み物を飲むようにしているのだが、暑くなるにつれて自動販売機の品ぞろえが冷たい飲み物一辺倒に変わってきている。冷たい飲み物を増やすのはよいのだが、温かい飲み物も少しぐらい残るといいのになぁ。）

_ プレプリント確認状況：arXiv:math 2月23日分まで、IACR ePrint 2012/331まで

_ 気になった論文：The Discrete Logarithm Problem in non-representable rings（Matan Banin and Boaz Tsaban, IACR Cryptology ePrint Archive 2012/320）

Bergman's Ring $E_p$, parameterized by a prime number $p$, is a ring with $p^5$ elements that cannot be embedded in a ring of matrices over any commutative ring. This ring was discovered in 1974. In 2011, Climent, Navarro and Tortosa described an efficient implementation of $E_p$ using simple modular arithmetic, and suggested that this ring may be a useful source for intractable cryptographic problems.

We present a deterministic polynomial time reduction of the Discrete Logarithm Problem in $E_p$ to the classical Discrete Logarithm Problem in $\Zp$, the $p$-element field. In particular, the Discrete Logarithm Problem in $E_p$ can be solved, by conventional computers, in sub-exponential time.

Along the way, we collect a number of useful basic reductions for the toolbox of discrete logarithm solvers.

何かに使いでがあるのかはわからないが、Bergman's Ringというものは初めて知った。

_ メモ：7月14日（土）に第３回選択公理オフがあるらしい。

_ （6/18記：一日中みっちり研究の議論をしていた。）

_ （6/18記：この日は代休を取ったので論文書きが捗った。）

_ （6/18記：お休み、といいつつ論文を書いていた。）

_ （6/18記：お休み、といいつつ論文を書いていた。）

_ （6/20記：今日も今日とて論文書き。「主定理の証明を書きながら定理の仮定を調整する」という書き方をしているため、主定理のステートメントが未だに固まらない。）

_ （6/20記：「『この詰将棋がすごい！』2012年度版　収録作家リスト」。完全に予想外だったので思わず二度見してしまった。）

_ （6/30記：今日も論文を書いていた。（以下、１週間ぐらい「今日も論文を書いていた」が続くので読まなくてよいです。））

_ （6/30記：今日も論文を書いていた。）

_ （6/30記：今日も論文を書いていた。）

_ （6/30記：今日も論文を書いていた。）

_ （6/30記：今日も論文を書いていた。）

_ （6/30記：今日も論文を書いていた。）

_ （6/30記：今日も論文を書いていた。）

_ （6/30記：今日も論文を書いていた。）

_ （6/30記：名古屋出張。打ち合わせ相手の某氏の通勤時間は私の20分の1ぐらいであることを知るなど。）

_ （6/30記：名古屋名物（？）小倉あんトーストに初挑戦してみたのだが、よく考えるとパンと餡子というのはあんパンの構成要素と同じであるわけで、食べた瞬間「ああ、これは包まれていないあんパンではないか」と気が付いて少々拍子抜けした。）

_ 論文の書き過ぎで10日分ぐらい日記を放り出していたことに気が付いた。