1996 | OriginalPaper | Chapter
Computing by homomorphic images
Author : Dipl.-Ing. Dr. Franz Winkler
Published in: Polynomial Algorithms in Computer Algebra
Publisher: Springer Vienna
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The Chinese remainder method has already been investigated by Chinese mathematicians more than 2000 years ago. For a short introduction to the history we refer to Knuth (1981). The main idea consists of solving a problem over the integers by solving this problem in several homomorphic images modulo various primes, and afterwards combining the solutions of the modular problems to a solution of the problem over the integers. In fact, the method can be generalized to work over arbitrary Euclidean domains, i.e., domains in which we can compute greatest common divisors by the Euclidean algorithm. An interesting list of different statements of the Chinese remainder theorem is given in Davis and Hersh (1981).