Factoring may be easier than we think (2016)

Re:Factoring may be easier than we think (2016) by baby on Monday July 01, 2019 @01:22AM (#20322652)

They are equivalent according to this: https://crypto.stackexchange.com/questions/9385/reduction-of...

[ Parent | on HN ]

Re:Factoring may be easier than we think (2016) by dvdkhlng on Monday July 01, 2019 @04:15AM (#20323400)

I think you are mistaken, they are not equivalent in any way that would be meaningful to assessing cryptographic strength.

The stack-exchange questions that you link to refers to [1] "Discrete Logarithms and Factoring". Section 1 "Introduction" already states many facts that imply that DLP is hard, even if you can factor:

* fastest known method for DLP is O(exp(c sqrt(log n log log n)))

* 1. 3c) "if we can factor in polynomial time, then to quickly solve a^x ≡ b mod n, all we need are solutions modulo the prime divisors of n"

Note that "solutions modulo the prime divisors of n" are still instances of the DLP with super-polynomial complexity, and in cryptographic applications N is usually a prime number anyway (DHE, ElGamal crypto-system), so 1 3c) does not actually apply.

See also the paper's section 6 final remarks "Conversely, one can ask for a fast algorithm for prime-modulus problems, assuming all needed factorizations. Both of these questions remain unanswered".

[1] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-186...

[ Parent | on HN ]

Re:Factoring may be easier than we think (2016) by Ar-Curunir on Monday July 01, 2019 @03:20AM (#20323155)

That for DLP modulo a composite, whereas Bitcoin uses DLP over elliptic curve groups.

[ Parent | on HN ]