 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||
| ||||||||||||||
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)
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.