Abstract
One of the key questions in contemporary applied cryptog- raphy is whether there exist an efficient algorithm for solving the dis- crete logarithm problem in elliptic curves. The primary approach for this problem is to try to solve a certain system of polynomial equations [46]. Current attempts try to solve them directly with existing software tools which does not work well due to their very loosely connected topology [45,42] and illusory reliance on degree falls [37]. A deeper reflection on what makes systems of algebraic equations efficiently solvable is missing. In this paper we propose a new approach for solving this type of polyno- mial systems which is radically different than current approaches, cf. [45, 42]. We carefully engineer systems of equations with excessively dense topology obtained from a complete clique/biclique graphs and hyper- graphs and unique special characteristics. We construct a sequence of systems of equations with a parameter K and argue that asymptot- ically when K grows the system of equations achieves a high level of saturation with limK→∞ F/T = 1 which allows to reduce the “regular- ity degree” and makes that polynomial equations over finite fields may become efficiently solvable.
Authors
Year
Journal
.
Keywords
Complex Systems, Computational Finance, and Cryptography