Recovery of algebraic numbers from their p-adic approximations

ABSTRACT

We describe three ways to generalize Lenstra's algebraic integer recovery method. One direction adapts the algorithm so that rational numbers are automatically produced given only upper bounds on the sizes of the numerators and denominators. Another direction produces a variant which recovers algebraic numbers as elements of multiple generator algebraic number fields. The third direction explains how the method can work if a reducible minimal polynomial had been given for an algebraic generator. Any two or all three of the generalizations may be employed simultaneously.

REFERENCES

• ABD86: J. A. Abbott , R. J. Bradford , J. H. Davenport, The Bath algebraic number package, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.250-253, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32490]
• FIK86: T. Freeman , G. Imirzian , E. Kaltofen, A system for manipulating polynomials given by straight-line programs, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.169-175, July 21-23, 1986, Waterloo, Ontario, Canada [doi>10.1145/32439.32473]
• H&W79: G H Hardy, and E M Wright, "An Introduction to the Theory of Numbers", Oxford Univ Press, 5th Ed (1979)
• KMS83: Erich Kaltofen , David R. Musser , B. David Saunders, A generalized class of polynomials that are hard to factor, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.188-194, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806394]
• Lenstra82: Arjen K. Lenstra, Lattices and Factorization of Polynomials over Algebraic Number Fields, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.32-39, April 05-07, 1982
• Lenstra83: Arjen K. Lenstra, Factoring polynominals over algebraic number fields, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.245-254, March 28-30, 1983
• LLL82: A K Lenstra, H W Lenstra and L Lovfisz, "Factoring Polynomials with Rational Coefficients", Math Ann 261 pp 515-534
• WGD82: Paul S. Wang , M. J. T. Guy , J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin, v.16 n.2, p.2-3, May 1982 [doi>10.1145/1089292.1089293]
• W&R76: P. J. Weinberger , L. P. Rothschild, Factoring Polynomials Over Algebraic Number Fields, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.335-350, Dec. 1976 [doi>10.1145/355705.355709]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory