HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Finding low-weight polynomial multiples using discrete logarithm

Abstract : Finding low-weight multiples of a binary polynomial is a difficult problem arising in the context of stream ciphers cryptanalysis. The classical algorithm to solve this problem is based on a time memory trade-off. We will present an improvement to this approach using discrete logarithm rather than a direct representation of the involved polynomials. This gives an algorithm which improves the theoretical complexity, and is also very flexible in practice.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

Contributor : Yann Laigle-Chapuy Connect in order to contact the contributor
Submitted on : Thursday, July 12, 2007 - 9:57:27 AM
Last modification on : Friday, February 4, 2022 - 3:10:00 AM
Long-term archiving on: : Thursday, September 23, 2010 - 4:09:46 PM


Files produced by the author(s)


  • HAL Id : inria-00123316, version 3
  • ARXIV : cs/0701069



Frédéric Didier, Yann Laigle-Chapuy. Finding low-weight polynomial multiples using discrete logarithm. IEEE International Symposium on Information Theory - ISIT'07, Jun 2007, Nice, France. ⟨inria-00123316v3⟩



Record views


Files downloads