講演抄録/キーワード |
講演名 |
2017-03-07 13:30
[招待講演]有限体上の多変数連立代数方程式系に対する総当り探索の打破 Daniel Lokshtanov(ベルゲン大)・Ramamohan Paturi(カリフォルニア大サンディエゴ校)・○玉置 卓(京大)・Ryan Williams(マサチューセッツ工科大)・Huacheng Yu(スタンフォード大) COMP2016-53 |
抄録 |
(和) |
有限体上の多変数連立代数方程式系を解くことは, 数学, 科学,および工学における基本的は問題である.
有限体の位数を$q$, 変数の個数を$n$とする.
このとき, $q^n$通りの解候補を総当たり探索することにより問題を解くことができる.
本研究では, 最悪時に $q^n$ より速い計算時間でこの問題を解く初めてのアルゴリズムを示す.
我々のアルゴリズムは解の個数を数えることもできる.
このアルゴリズムの計算時間は, 方程式の最大次数が$d$の場合, およそ $q^{n(1-1/O(d))}$ である.
本研究では, 方程式が多項式ではなくある種の算術回路で定義されるような一般化された問題も扱い, それに対するアルゴリズムも与える. |
(英) |
Solving systems of multivariate polynomial equations over finite fields is a fundamental problem in mathematics, science and engineering.
Let $q$ be the order of the underlying field and $n$ be the number of variables.
Then, the problem can be solved by the brute force search over $q^n$ possible solutions.
We present the first algorithm that solves the problem in time faster than $q^n$ in the worst-case.
Our algorithm can count the number of solutions as well.
The running time of the algorithm is roughly of the form $q^{n(1-1/O(d))}$, where $d$ is the maximum degree of polynomials.
We also consider a generalization of the problem, where each equation is defined by a certain type of arithmetic circuit, and give an algorithm for the generalized problem. |
キーワード |
(和) |
指数時間アルゴリズム / 多項式 / 低次数 / 算術回路 / / / / |
(英) |
exponential time algorithm / polynomial / low degree / arithmetic circuit / / / / |
文献情報 |
信学技報, vol. 116, no. 503, COMP2016-53, pp. 19-19, 2017年3月. |
資料番号 |
COMP2016-53 |
発行日 |
2017-02-28 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-53 |
|