Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

The use of bad primes in rational reconstruction


Authors: Janko Böhm, Wolfram Decker, Claus Fieker and Gerhard Pfister
Journal: Math. Comp. 84 (2015), 3013-3027
MSC (2010): Primary 13P10, 68W10; Secondary 52C05
Published electronically: April 15, 2015
MathSciNet review: 3378860
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A standard method for finding a rational number from its values modulo a collection of primes is to determine its value modulo the product of the primes via Chinese remaindering, and then use Farey sequences for rational reconstruction. Successively enlarging the set of primes if needed, this method is guaranteed to work if we restrict ourselves to ``good'' primes. Depending on the particular application, however, there may be no efficient way of identifying good primes.

In the algebraic and geometric applications we have in mind, the final result consists of an a priori unknown ideal (or module) which is found via a construction yielding the (reduced) Gröbner basis of the ideal. In this context, we discuss a general setup for modular and, thus, potentially parallel algorithms which can handle ``bad'' primes. A new key ingredient is an error tolerant algorithm for rational reconstruction via Gaussian reduction.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 13P10, 68W10, 52C05

Retrieve articles in all journals with MSC (2010): 13P10, 68W10, 52C05


Additional Information

Janko Böhm
Affiliation: Fachbereich Mathematik, Technical University Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany
Email: boehm@mathematik.uni-kl.de

Wolfram Decker
Affiliation: Fachbereich Mathematik, Technical University Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany
Email: decker@mathematik.uni-kl.de

Claus Fieker
Affiliation: Fachbereich Mathematik, Technical University Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany
Email: fieker@mathematik.uni-kl.de

Gerhard Pfister
Affiliation: Fachbereich Mathematik, Technical University Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany
Email: pfister@mathematik.uni-kl.de

DOI: https://doi.org/10.1090/mcom/2951
Keywords: Rational reconstruction, Farey map
Received by editor(s): July 16, 2012
Received by editor(s) in revised form: September 27, 2013, and March 24, 2014
Published electronically: April 15, 2015
Article copyright: © Copyright 2015 American Mathematical Society