Electronic Proceedings in Theoretical Computer Science (Mar 2014)

Computing discrete logarithm by interval-valued paradigm

  • Benedek Nagy,
  • Sándor Vályi

DOI
https://doi.org/10.4204/EPTCS.143.7
Journal volume & issue
Vol. 143, no. Proc. DCM 2012
pp. 76 – 86

Abstract

Read online

Interval-valued computing is a relatively new computing paradigm. It uses finitely many interval segments over the unit interval in a computation as data structure. The satisfiability of Quantified Boolean formulae and other hard problems, like integer factorization, can be solved in an effective way by its massive parallelism. The discrete logarithm problem plays an important role in practice, there are cryptographical methods based on its computational hardness. In this paper we show that the discrete logarithm problem is computable by an interval-valued computing in a polynomial number of steps (within this paradigm).