Talk:Coppersmith's Attack

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Cryptography / Computer science  (Rated B-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the quality scale.
 High  This article has been rated as High-importance on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science (marked as High-importance).
 

I think there's a mistake in Theorem 1 (Coppersmith): Instead of X = N^(1/4 - eps) for eps ≤ 0 I think it should be X = N^(1/d - eps) for eps ≥ 0


It says that using e = 2^16 + 1 takes only 17 multiplications as opposed to over 1000 when a random e of similar size is used; surely using successive squaring, a random e of similar size would only take at most 31 multiplications or thereabouts? Julian Gilbey (talk) 10:45, 4 October 2011 (UTC)

I updated the article to reflect this. 2001:470:D08D:0:0:0:0:1 (talk) 00:34, 6 July 2013 (UTC)

No, it's still wrong. You need *5* multiplications for 65537, and I don't know how to correctly calculate the number required for a random e of similar size. 2001:470:D08D:0:0:0:0:1 (talk) 18:46, 7 July 2013 (UTC)

Ok, 17 is correct, and the original statement was a misquote from the boneh paper, which claims 1000 multiplications for an e of similar size to N. 2001:470:1F0A:B09:0:0:0:2 (talk) 10:45, 10 July 2013 (UTC)