Quote:
Originally Posted by ATH
I tried using the GMP function mpz_powm to calculate 3^{2[sup]2^(n1)}[/sup] mod F_{n}=2^{2[sup]n}[/sup]+1 and timed it:
n=14: 1.945s
n=15: 12.143s
n=16: 73.373s
n=17: 415.121s
this suggest the time is roughly 2.6*10^{11} * 5.98^{n} with R^{2} = 0.9999225.
This means n=25 would take roughly 7*10^{8} sec ~ 22 years.

By FFT that should be O(4^n*n*log(n)).