On Thu, May 15, 2008 at 02:00:25AM +0200, Steinar H. Gunderson wrote:
On Wed, May 14, 2008 at 11:12:26PM +0000, brian m. carlson wrote:If one can solve the Discrete Logarithm Problem, then one can factor, but the reverse is not true.This is the first time I've ever heard anyone claim this; I've seen people and textbooks claim they're roughly equivalent, but not that this is a one-way street. Do you have any references?
I read it somewhere, probably on a PGP forum, but apparently that was incorrect. According to http://portal.acm.org/citation.cfm?id=894497 : To summarize: solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes. I stand corrected. -- brian m. carlson / brian with sandals: Houston, Texas, US +1 713 440 7475 | http://crustytoothpaste.ath.cx/~bmc | My opinion only troff on top of XML: http://crustytoothpaste.ath.cx/~bmc/code/thwack OpenPGP: RSA v4 4096b 88AC E9B2 9196 305B A994 7552 F1BA 225C 0223 B187
Description: Digital signature