はじめに
初めまして、数理科学専攻の大学院生kotaと申します。
この度研究の週誌的なものを書いてみようと思いましたー。
目次
研究概要
皆さんは量子コンピュータは聞いたことあると思いますが、そのコンピュータによってRSA暗号の計算量的困難性が危ぶまれています。
Shoreさんのお陰というか素因数分解アルゴリズムのせいですね...
そこで多変数公開鍵暗号というものがあってとても便利なわけです!
暗号化はとても簡単で例えば
$f_1(x_1, x_2) = x_1^2 + 2 x_1x_2 + 11x_2^2$
という式があるとしたら$x_1, x_2$をmod 31の世界で整数を代入してそれをメッセージ(暗号化したい文章)にしてしまおうというものです。 mod 31なのは$F_{31}$という有限体を使うからですね。
というわけでこれを連立させて方程式を解くのが難しいよっていうのが計算量的困難性になります!
本当にそうだろうか?ということでゴリゴリ解いて最速アルゴリズムを見つけて解けないならばこの暗号は使える!っていうのを目指すのが研究の目標です...
グレブナー基底について
連立代数方程式を簡単に解くものにグレブナ基底計算がありますと
それをどれだけ早く計算できるかが鍵な訳です...
ちょっと例を見てみましょう!
例えば
\left\{
\begin{array}{ll}
f = 2 x + 2 * y - 2 \\
g = 2 x + y + 1
\end{array}
\right.
この方程式を解きたいなって思った時、皆さんはガウスの消去法をなんとなくやるでしょう...
そんなとき
グレブナー基底
R.<x, y> = QQ['x, y']
f = 2 * x + 2 * y - 2
g = 2 * x + y + 1
I = (f, g)*R; I # fとgから生成されるイデアル(f, g)をIとします。
Ideal (2*x + 2*y - 2, 2*x + y + 1) of Multivariate Polynomial Ring in x, y over Rational Field
I.groebner_basis() #Iのグレブナ基底はこうなります.
[x + 2, y - 3]
このように x+2とy-3がグレブナー基底になるわけです。
\left\{
\begin{array}{ll}
x + 2 = 0 <=> x = -2 \\
y - 3 = 0 <=> y = 3
\end{array}
\right.
グレブナー基底計算によりすぐに連立方程式の解が、、、
# 使用アルゴリズムについて という風にこの計算アルゴリズムは多分ブッフバーガーさんのものが使われている(sagemathに聞いてください) と思うのですが他にもアルゴリズムがあります。 早いアルゴリズムの研究が僕の研究です。 # これから二週間か一週間に一回研究の成果や数学に関するprogrammingについての記事を書いていきます. # ご期待ください.参考文献
ごめんなさい特にないです...