A stable integer relation algorithm
- We study the following problem: given x element Rn either find a short integer relation m element Zn, so that =0 holds for the inner product <.,.>, or prove that no short integer relation exists for x. Hastad, Just Lagarias and Schnorr (1989) give a polynomial time algorithm for the problem. We present a stable variation of the HJLS--algorithm that preserves lower bounds on lambda(x) for infinitesimal changes of x. Given x \in {\RR}^n and \alpha \in \NN this algorithm finds a nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no very short relation exists for points \bar{x} within half the x'--distance from x. On the other hand if x'=x then m is, up to a factor 2^{n/2}, a shortest integer relation for \mbox{x.} Our algorithm uses, for arbitrary real input x, at most \mbox{O(n^4(n+\log \alpha))} many arithmetical operations on real numbers. If x is rational the algorithm operates on integers having at most \mbox{O(n^5+n^3 (\log \alpha)^2 + \log (\|q x\|^2))} many bits where q is the common denominator for x.
Verfasserangaben: | Claus Peter SchnorrGND, Carsten Rössner |
---|---|
URN: | urn:nbn:de:hebis:30-12327 |
URL: | http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
Titel des übergeordneten Werkes (Deutsch): | Technical Report 94-016, ICSI, Berkeley, CA, 1994 |
Verlagsort: | Frankfurt am Main |
Dokumentart: | Bericht |
Sprache: | Englisch |
Datum der Veröffentlichung (online): | 13.07.2005 |
Jahr der Erstveröffentlichung: | 1994 |
Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Datum der Freischaltung: | 13.07.2005 |
Ausgabe / Heft: | April 1994 |
Seitenzahl: | 13 |
Quelle: | Technical Report 94-016, ICSI, Berkeley, CA, 1994 , http://www.mi.informatik.uni-frankfurt.de/research/papers.html |
HeBIS-PPN: | 416392954 |
Institute: | Informatik und Mathematik / Mathematik |
Informatik und Mathematik / Informatik | |
DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Deutsches Urheberrecht |