Computing discrete logarithm by interval-valued paradigm

Benedek Nagy
Sándor Vályi

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).

In Benedikt Löwe and Glynn Winskel: Proceedings 8th International Workshop on Developments in Computational Models (DCM 2012), Cambridge, United Kingdom, 17 June 2012, Electronic Proceedings in Theoretical Computer Science 143, pp. 76–86.
Published: 29th March 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.143.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org