Skip to main content
MathOverflow

Return to Answer

Fixed typos
Source Link
Victor Miller
Victor Miller
  • 4.6k
  • 4
  • 36
  • 52

As the previous answers have stated the map from $F_n \rightarrow n$ is essentially a logarithm. Since the binary representation of $F_n$ has about $c n$ bits (for the appropriate constant $c = \log_2 \phi$, where $\phi = (-1+\sqrt{5})/2$$\phi = (1+\sqrt{5})/2$), the bit complexity of calculating the logarithms is about $c' \log^2 n$, for some constant $c$$c'$. Here's another simpler method which has the same complexity:

If you are given $F_n$ for some unknown $n$ if you knew $F_{n-1}$ with $n$ subtractions you can find out what $n$ is (run the fibonacci recursion in reverse). But $F_n/F_{n-1} \approx \phi$. So if you know $1/\phi$ to about $2n$ bits of precision you can find $F_{n-1}$ by multiplying by $1/\phi$ and rounding to the nearest integer. This calculation is certainly simpler than taking logs.

Another alternative is to take $p$-adic logarithms: the function $n \rightarrow F_n$ is $p$-adically continuous, so since $\mathbb{Z}$ is dense in $\mathbb{Z}_p$ it defines a unique $p$-adically continuous function, which by a criterion of Mahler is analytic. You can invert the function via Newton's method -- you just need to find the answer mod $p$ to get a starting point.

As the previous answers have stated the map from $F_n \rightarrow n$ is essentially a logarithm. Since the binary representation of $F_n$ has about $c n$ bits (for the appropriate constant $c = \log_2 \phi$, where $\phi = (-1+\sqrt{5})/2$, the bit complexity of calculating the logarithms is about $c' \log^2 n$, for some constant $c$. Here's another simpler method which has the same complexity:

If you are given $F_n$ for some unknown $n$ if you knew $F_{n-1}$ with $n$ subtractions you can find out what $n$ is (run the fibonacci recursion in reverse). But $F_n/F_{n-1} \approx \phi$. So if you know $1/\phi$ to about $2n$ bits of precision you can find $F_{n-1}$ by multiplying by $1/\phi$ and rounding to the nearest integer. This calculation is certainly simpler than taking logs.

Another alternative is to take $p$-adic logarithms: the function $n \rightarrow F_n$ is $p$-adically continuous, so since $\mathbb{Z}$ is dense in $\mathbb{Z}_p$ it defines a unique $p$-adically continuous function, which by a criterion of Mahler is analytic. You can invert the function via Newton's method -- you just need to find the answer mod $p$ to get a starting point.

As the previous answers have stated the map from $F_n \rightarrow n$ is essentially a logarithm. Since the binary representation of $F_n$ has about $c n$ bits (for the appropriate constant $c = \log_2 \phi$, where $\phi = (1+\sqrt{5})/2$), the bit complexity of calculating the logarithms is about $c' \log^2 n$, for some constant $c'$. Here's another simpler method which has the same complexity:

If you are given $F_n$ for some unknown $n$ if you knew $F_{n-1}$ with $n$ subtractions you can find out what $n$ is (run the fibonacci recursion in reverse). But $F_n/F_{n-1} \approx \phi$. So if you know $1/\phi$ to about $2n$ bits of precision you can find $F_{n-1}$ by multiplying by $1/\phi$ and rounding to the nearest integer. This calculation is certainly simpler than taking logs.

Another alternative is to take $p$-adic logarithms: the function $n \rightarrow F_n$ is $p$-adically continuous, so since $\mathbb{Z}$ is dense in $\mathbb{Z}_p$ it defines a unique $p$-adically continuous function, which by a criterion of Mahler is analytic. You can invert the function via Newton's method -- you just need to find the answer mod $p$ to get a starting point.

Source Link
Victor Miller
Victor Miller
  • 4.6k
  • 4
  • 36
  • 52

As the previous answers have stated the map from $F_n \rightarrow n$ is essentially a logarithm. Since the binary representation of $F_n$ has about $c n$ bits (for the appropriate constant $c = \log_2 \phi$, where $\phi = (-1+\sqrt{5})/2$, the bit complexity of calculating the logarithms is about $c' \log^2 n$, for some constant $c$. Here's another simpler method which has the same complexity:

If you are given $F_n$ for some unknown $n$ if you knew $F_{n-1}$ with $n$ subtractions you can find out what $n$ is (run the fibonacci recursion in reverse). But $F_n/F_{n-1} \approx \phi$. So if you know $1/\phi$ to about $2n$ bits of precision you can find $F_{n-1}$ by multiplying by $1/\phi$ and rounding to the nearest integer. This calculation is certainly simpler than taking logs.

Another alternative is to take $p$-adic logarithms: the function $n \rightarrow F_n$ is $p$-adically continuous, so since $\mathbb{Z}$ is dense in $\mathbb{Z}_p$ it defines a unique $p$-adically continuous function, which by a criterion of Mahler is analytic. You can invert the function via Newton's method -- you just need to find the answer mod $p$ to get a starting point.