Abstract | ||
---|---|---|
We present algorithms, which when given a real vector x
2\fracn -</font
> 222^{\frac{{n - 2}}{2}}
times longer than the length of the shortest relation for x. Given a rational input xn this algorithm halts in polynomially many bit operations. The basic algorithm of this kind is due to Ferguson and Forcade (1979) and is closely related to the Lovàsz (1982) lattice basis reduction algorithm. |
Year | DOI | Venue |
---|---|---|
1986 | 10.1007/3-540-16078-7_69 | SIAM J. Comput. |
Keywords | Field | DocType |
diophantine approximation,lattice basis reduction | Integer,Discrete mathematics,Combinatorics,Square-free polynomial,Degree of a polynomial,Algorithm,Integer relation algorithm,Polynomial remainder theorem,Homogeneous polynomial,Irreducible polynomial,Mathematics,Lattice reduction | Conference |
Volume | Issue | ISBN |
18 | 5 | 3-540-16078-7 |
Citations | PageRank | References |
48 | 17.77 | 1 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Johan Håstad | 1 | 3586 | 557.23 |
B. Just | 2 | 48 | 17.77 |
J. C. Lagarias | 3 | 563 | 235.61 |
C. P. Schnorr | 4 | 379 | 95.27 |