Exercise 4.1.21* (About Fermat's method of factorization)

Question

Let $n$ be an odd positive integer. If $n$ factors into the product of two integers, $n = uv$, with $u>v$ and $u - v \leq \sqrt[4]{64n}$, prove that the roots of $x^2 - 2 \lfloor \sqrt{n} + 1 \rfloor x +n = 0$ are integers.

\bigskip
Hint. Use the identity $\{(u+v)/2\}^2 - \{(u-v)/2\}^2 = uv$ to get bounds on the integer $(u+v)/2$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}} ewcommand{\N}{\mathbb{N}} ewcommand{\R}{\mathbb{R}} \begin{proof} By hypothesis, $$n = uv = \left( \frac{u+v}{2} ight)^2 - \left(\frac{u-v}{2} ight)^2.$$ Since $n$ is odd, $u$ and $v$ are odd, so $(u+v)/2$ and $(u-v)/2$ are integers. We know also that $u- v \leq \sqrt[4]{64n}$, thus $(u-v)/2 \leq \sqrt[4]{4n}$, and $u>v$, so $$ 0 < \left(\frac{u-v}{2} ight)^2 \leq 2 \sqrt{n}.$$ This gives the inequalities $$n < \left(\frac{u+v}{2} ight)^2 \leq n + \left(\frac{u-v}{2} ight)^2 \leq n + 2 \sqrt{n}.$$ Therefore $$\sqrt{n} < \frac{u+v}{2} \leq \sqrt{n+ 2 \sqrt{n}},$$ or equivalently \begin{align} 0 < \frac{u+v}{2} - \sqrt{n} \leq \sqrt{n+ 2 \sqrt{n}} - \sqrt{n}. \end{align} Moreover, since $\sqrt{n+ 2 \sqrt{n}} > \sqrt{n}$, \begin{align*} \sqrt{n+ 2 \sqrt{n}} - \sqrt{n} &= \frac{2 \sqrt{n}}{\sqrt{n+ 2 \sqrt{n}} + \sqrt{n}}\ &<\frac{2 \sqrt{n}}{2 \sqrt{n}} = 1. \end{align*} Then the inequalities (1) give \begin{align*} \frac{u+v}{2} - 1 \leq \sqrt{n} < \frac{u+v}{2}, \end{align*} where $\frac{u+v}{2}$ is an integer, so \begin{align} \lfloor \sqrt{n} floor = \frac{u+v}{2} - 1. \end{align} Then $ \frac{u+v}{2} = \lfloor \sqrt{n} floor + 1 = \lfloor \sqrt{n} + 1 floor$. The relations $$ \left\{ \begin{array}{ll} u + v &= 2 \lfloor \sqrt{n} + 1 floor,\ uv &= n, \end{array} ight. $$ show that the integers $u$ and $v$ are the roots of $$(x- u) (x-v ) = x^2 - (u+v) x + uv = x^2 - 2 \lfloor \sqrt{n} + 1 floor x +n = 0.$$ If $n = uv$, with $u>v$ and $u - v \leq \sqrt[4]{64n}$, the roots of $x^2 - 2 \lfloor \sqrt{n} + 1 floor x +n = 0$ are integers. \end{proof} Note: This problem seems related to Fermat's method to factor an integer $n$ by representing $n$ as difference of two squares. This method is efficient if the factors $u, v$ are close. To choose two primes numbers $u, v$ for the RSA method in cryptography, it is dangerous to take $u$ and $v $ too close. To give a (very little) example, take $n = 47070339749$. Then $\lfloor \sqrt{n} floor = 216956$, $2\lfloor \sqrt{n} + 1 floor = 433914$, and the previous equation $$x^2 - 2 \lfloor \sqrt{n} + 1 floor x +n = x^2 - 433914\, x + 47070339749 = 0$$ has for solutions the two integers $216967$ and $216947$: \begin{verbatim} sage: solve(x^2 - 433914*x + 47070339749, x) [x == 216967, x == 216947] \end{verbatim} so $$n = 47070339749 = 216967 imes 216947,$$ and the code is deciphered. (To find the decomposition $n = uv = a^2 -b^2$, we can also find $u = a+b $ and $v = a-b$ by increasing $a$, starting from $a = \lceil \sqrt{n} ceil = 216957$, $b =0$, and increasing $b$ until $a^2 - b^2 < n$.)

Exercise 4.1.21* (About Fermat's method of factorization)

Answers

Comments

Exercise 4.1.21* (About Fermat's method of factorization)

Answers

Comments

Add answer