Polynomial solution to Discrete Logarithm Problem in Interval-valued computing

Loading...
Thumbnail Image

Journal Title

Journal ISSN

Volume Title

Publisher

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.

Description

Citation

Endorsement

Review

Supplemented By

Referenced By