Generate the worst case 256-bit input for GCD

Question

Is there a fast method for generating the worst case 256-bit input for GCD?

According to this Wikipedia article, the worst case for GCD is when the inputs are consecutive Fibonacci numbers.

However, how exactly can I find the largest pair of consecutive Fibonacci numbers which are at most $2^{256}-1$?

Thank you!

Answer 1

$$ F_{370} = 94611056096305838013295371573764256526437182762229865607320618320\ 601813254535$$

is largest, smaller than $2^{256} -1$

Answer 2

Fibonacci numbers have a closed form formula:

$$ F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right). $$

Since $\frac{1+\sqrt{5}}{2}>1$ and $\left|\frac{1-\sqrt{5}}{2}\right|<1$, for large $n$, $$ F_n\approx\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n. $$

Now, you can take a logarithm to estimate the value of $n$. In particular, we want $$ n\ln\left(\frac{1+\sqrt{5}}{2}\right)-\ln\sqrt{5}<256\ln 2. $$ Solving for $n$, we get $$ n<370.41... $$

Therefore, the largest Fibonacci number would be $F_{370}$. You can then estimate this with the closed form formula or its approximation (the correction term is on the order of $10^{-78}$).