Talk:Coppersmith's attack

Cryptography: Computer science High‑importance

	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.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed 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)[reply]

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

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)[reply]

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)[reply]