TAOCP 4.5.4 Exercise 11
Algorithm E is the continued-fraction factoring method applied to $\sqrt{kN}$.
Section 4.5.4: Factoring into Primes
Exercise 11. [M20] What outputs does Algorithm E give when $N = 197209$, $k = 5$, $m = 1$? [Hint: $\sqrt{5 \cdot 197209} \approx 992 + \frac{1}{1.495}, \frac{1}{2.495}, \frac{1}{2.495}, \frac{1}{1.984} \cdots]$
Verified: yes
Solve time: 3m01s
Solution
Algorithm E is the continued-fraction factoring method applied to $\sqrt{kN}$.
For
$$ N=197209,\qquad k=5,\qquad m=1, $$
we have
$$ kN=986045, $$
and
$$ \sqrt{986045}=992+\cfrac1{1.495\ldots} =992+\cfrac1{1+\cfrac1{2.495\ldots}} = [,992;\overline{1,495,2,495,1,1984},]. $$
The successive convergents are
$$ \frac{992}{1},\quad \frac{993}{1},\quad \frac{492527}{496},\quad \frac{986047}{993},\quad \frac{488585792}{492031},\quad \frac{489571839}{493024}. $$
Algorithm E forms the quantities
$$ Q_j=p_j^{,2}-986045,q_j^{,2}, $$
giving
$$ Q_1=4,\qquad Q_2=-991,\qquad Q_3=4,\qquad Q_4=-1981,\qquad Q_5=1. $$
The appearance of
$$ Q_5=1 $$
yields
$$ 489571839^{,2}-986045\cdot 493024^{,2}=1. $$
Since $986045=5N$, this gives
$$ 489571839^{,2}\equiv 1 \pmod N. $$
Therefore
$$ (489571839-1)(489571839+1)\equiv 0 \pmod N, $$
and Algorithm E outputs the nontrivial factors obtained from
$$ \gcd(489571839-1,,197209) \quad\text{and}\quad \gcd(489571839+1,,197209). $$
These are
$$ \gcd(489571838,197209)=991, $$
and
$$ \gcd(489571840,197209)=199. $$
Hence the outputs are the factors
$$ 199,\qquad 991, $$
and
$$ 197209=199\cdot 991. $$
$$ \boxed{197209=199\cdot 991} $$