Polynomial solution to Discrete Logarithm Problem in Interval-valued computing

Abstract

We show that discrete logarithm can be computed in the frame- work of interval-valued computations by a polynomial computation. This new com- puting device is of highly parallel nature: it operates on so-called interval- values which are nite unions of subintervals of [0,1) and constitute an in - nite Boolean algebra. The computation process is modelled in the style of Boolean networks but some non-Boolean operators are also allowed: shifts in both directions and a kind of zooming called product. This paradigm in an restricted form has the computation power of PSPACE as shown in [1] when it is used to decision problems. In [2] it is de ned how interval-valued computa- tions can be used to calculate discrete functions. In that paper the prime factorization was shown to be computable by a quadratic size interval-valued computation. The calculation of discrete logarithm also an important topic of cryptography. In this talk, we demonstrate an analogous result for the calculation of discrete logarithm.