Computing the $M = U U^t$ integer matrix decomposition

Nigel Smart, Katharina Geissler

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

The cryptanalysis of Gentry and Szydlo of the revised NTRU signature scheme requires the computation of the integer matrix decomposition $M = U U^t$. We propose a heuristic algorithm to compute this decomposition and investigate its properties. Our test implementation of this algorithm in Magma is able to deal with matrices up to $158$ rows and columns.
Translated title of the contributionComputing the $M = U U^t$ integer matrix decomposition
Original languageEnglish
Title of host publication Cryptography and Coding - IMACC 2003
PublisherSpringer Berlin Heidelberg
Pages223 - 233
Number of pages10
Volume2898
Publication statusPublished - Dec 2003

Bibliographical note

Conference Proceedings/Title of Journal: Proc. Cryptography and Coding

Fingerprint Dive into the research topics of 'Computing the $M = U U^t$ integer matrix decomposition'. Together they form a unique fingerprint.

  • Cite this

    Smart, N., & Geissler, K. (2003). Computing the $M = U U^t$ integer matrix decomposition. In Cryptography and Coding - IMACC 2003 (Vol. 2898, pp. 223 - 233). Springer Berlin Heidelberg. http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000027