Consecutive smooth number generator recovery

176 Views Asked by At

The numbers $n=811150370266636218705704$ and $n+1$ have highest factors 173 and 167, and they happen to be the largest consecutive 173-smooth numbers.

They were found via Størmer's theorem and the continued fraction method for solving the Pell equation. That means $n$ was generated from the numerator of a convergent fraction that solves $x^2 - 2 \sqrt{k} y^2 =1$.

Out of the $2^{40} = 1099511627776$ possibilities, what was $k$? Is there a way to go backwards other than brute force?

1

There are 1 best solutions below

1
On BEST ANSWER

Lehmer's procedure involves solving the Pell equation $$x^2-2qy^2=1$$ for $173$-smooth squarefree $q\neq2$. (This makes $\frac{x}{y}$ an approximation for $\sqrt{2q}$.) Then, for a finite number of smallest solutions $(x,y)$ of each Pell equation, the integers $n=\frac{x-1}{2}$ and $n+1$ are tested for smoothness.

Therefore, the $x$ involved is $x=2n+1$, and the $q$ involved is exactly the squarefree part of $qy^2 = \frac{x^2-1}{2} = 2n(n+1)$, that is, the factor of $2n(n+1)$ with largest square cofactor. That cofactor is $y^2$. Plugging in, we get $$\begin{align} qy^2 = 2n(n+1) &= 2^4\cdot3^3\cdot5\cdot7^2\cdot13\cdot19\cdot23^2\cdot43\cdot47^2 \cdot59\cdot61\cdot71\cdot83\cdot89 \\&\qquad\cdot103\cdot107\cdot109\cdot139\cdot151^2\cdot167^3\cdot173^2 \\\therefore\quad q &= 3\cdot5\cdot13\cdot19\cdot43\cdot59\cdot61\cdot71\cdot83\cdot89 \cdot103\cdot107\cdot109\cdot139\cdot167 \end{align}$$ I hope this answers your question.