Talk:Naccache–Stern knapsack cryptosystem

Cryptography: Computer science Mid‑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
Mid	This article has been rated as Mid-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Mid-importance).

As the authors themselves point out, other knapsack cryptosystems have not fared so well. Does anyone know of any breaks on this one? The authors issue a challenge (with prize) at the end of their paper, has this prize been claimed?

--Beamishboy 15:37, 28 July 2006 (UTC)[reply]

I am removing the reference to the pohlig-hellman algorithm. I understand that the authors mention it in their original paper; however, no one would use the pohlig-hellman algorithm to generate the roots v_i. The element s is already noted to be coprime with p-1. Thus raising the p_i to the inverse of s modulo p-1 would be sufficient and very fast.

The other reason that I am removing the reference to pohlig-hellman is because it forces the reader to infer that the primes used in the Naccache Stern system are required to have a smooth totient. This, I had to read the original paper before I knew, is not the case at all. In fact, having p-1 smooth makes the system vulnerable DUE TO pohlig-hellman.

--Gtg207u (talk) 20:59, 30 December 2008 (UTC)[reply]