Polynomial solution to Discrete Logarithm Problem in Interval-valued computing
Loading...
Date
Authors
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.