[Cryptography] MATH: Unlikely correctness of paper will break some discrete logarithm over F_p^*
Georgi Guninski
guninski at guninski.com
Wed Aug 31 04:33:25 EDT 2016
https://arxiv.org/abs/1608.07032
The Discrete Logarithm Problem over Prime Fields can be
transformed to a Linear Multivariable Chinese Remainder
Theorem
H. Gopalakrishna Gadiyar, R. Padma
(Submitted on 25 Aug 2016)
I am pretty sure if this paper is fixable, it will efficiently break
DLs over F_p^* at least for primes of the form p=2q+1 with q prime.
Is the paper fixable?
How would it break IMHO:
The authors claim (18) (19) that they reduce DL to two constrained
linear congruences with different moduli in the two unknowns
n,\beta_n and the constraints are 0 < n < p, 0 < \beta_n < p.
This is efficiently solvable via integer programming due to result
of Lenstra about integer linear programs in fixed number of variables.
Work over the integers adding two integer unknowns $x,y$ to get rid
of the congruences and keep the inequality constraints, getting
integer program in _only four unknowns_.
Shorter version of this was posted few days ago on cpunks.org, no
replies so far.
The authors don't appear to be cranks/crackpots, though
scholar.google.com doesn't recognize them AFAICT.
More information about the cryptography
mailing list