# A Stable Integer Relation Algorithm

Title | A Stable Integer Relation Algorithm |

Publication Type | Technical Report |

Year of Publication | 1994 |

Authors | Rössner, C., & Schnorr C. P. |

Other Numbers | 886 |

Abstract | We study the following problem: given x ? 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 ar{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. |

URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-016.pdf |

Bibliographic Notes | ICSI Technical Report TR-94-016 |

Abbreviated Authors | C. Rössner and C. P. Schnorr |

ICSI Publication Type | Technical Report |