View Single Post
Old 2011-03-24, 02:32   #11
R. Gerbicz
R. Gerbicz's Avatar
"Robert Gerbicz"
Oct 2005

101011101012 Posts

Originally Posted by ATH View Post
I tried using the GMP function mpz_powm to calculate 32[sup]2^(n-1)[/sup] mod Fn=22[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.98n with R2 = 0.9999225.

This means n=25 would take roughly 7*108 sec ~ 22 years.
By FFT that should be O(4^n*n*log(n)).
R. Gerbicz is offline   Reply With Quote