All published worksheets from http://sagenb.org
Image: ubuntu2004
File: /usr/local/sage2/local/lib/python2.6/site-packages/sage/rings/arith.py
Type: <type ‘function’>
Definition: rational_reconstruction(a, m, algorithm=’fast’)
Docstring:
This function tries to compute x/y, where x/y is a rational number in lowest terms such that the reduction of x/y modulo m is equal to a and the absolute values of x and y are both \le \sqrt{m/2}. If such x/y exists, that pair is unique and this function returns it. If no such pair exists, this function raises ZeroDivisionError.
An efficient algorithm for computing rational reconstruction is very similar to the extended Euclidean algorithm. For more details, see Knuth, Vol 2, 3rd ed, pages 656-657.
INPUT:
- a - an integer
- m - a modulus
- algorithm - (default: ‘fast’)
- 'fast' - a fast compiled implementation
- 'python' - a slow pure python implementation
OUTPUT:
Numerator and denominator n, d of the unique rational number r=n/d, if it exists, with n and |d| \le \sqrt{N/2}. Return (0,0) if no such number exists.
The algorithm for rational reconstruction is described (with a complete nontrivial proof) on pages 656-657 of Knuth, Vol 2, 3rd ed. as the solution to exercise 51 on page 379. See in particular the conclusion paragraph right in the middle of page 657, which describes the algorithm thus:
This discussion proves that the problem can be solved efficiently by applying Algorithm 4.5.2X with u=m and v=a, but with the following replacement for step X2: If v3 \le \sqrt{m/2}, the algorithm terminates. The pair (x,y)=(|v2|,v3*\mathrm{sign}(v2)) is then the unique solution, provided that x and y are coprime and x \le \sqrt{m/2}; otherwise there is no solution. (Alg 4.5.2X is the extended Euclidean algorithm.)Knuth remarks that this algorithm is due to Wang, Kornerup, and Gregory from around 1983.
EXAMPLES:
sage: m = 100000 sage: (119*inverse_mod(53,m))%m 11323 sage: rational_reconstruction(11323,m) 119/53sage: rational_reconstruction(400,1000) ... ValueError: Rational reconstruction of 400 (mod 1000) does not exist.sage: rational_reconstruction(3,292393, algorithm='python') 3 sage: a = Integers(292393)(45/97); a 204977 sage: rational_reconstruction(a,292393, algorithm='python') 45/97 sage: a = Integers(292393)(45/97); a 204977 sage: rational_reconstruction(a,292393, algorithm='fast') 45/97 sage: rational_reconstruction(293048,292393, algorithm='fast') ... ValueError: Rational reconstruction of 655 (mod 292393) does not exist. sage: rational_reconstruction(293048,292393, algorithm='python') ... ValueError: Rational reconstruction of 655 (mod 292393) does not exist.