View Single Post
Old 2005-08-18, 12:18   #1
mpenguin
 
Aug 2005

178 Posts
Default Closed form solution of x^2 = 2 mod Fermat number

Sorry if this is known, but didn't find it on the net.
The solution of x^2 = I in C leads to solution to x^2 = 2 mod (2^(2^n)+1).
It is also possible to compute sqrt(2+sqrt(2)) mod (2^(2^n)+1) and
similar roots rising from solutions in C.

Any use of this?

--Code--
n0:=8;
n:=2^(2^n0)+1;
ii:=powermod(2,2^(n0-1),n);
ii2:=powermod(2,2^(n0-2),n);
ii3:=powermod(2,2^(n0-3),n);
sq2:=mods(ii2*2/(1+ii),n); /* sq2^2 mod n == 2*/
sq2a:=mods(ii3*2/((ii*sq2+1-ii)),n); /* sqrt(2+sqrt(2)) mod n*/
print("ii",ii,mods(ii^2,n),ii2,mods(ii2^2,n),"sqrt(2)=",sq2,
"sqrt(2)^2=",mods(sq2^2,n),"sqrt(2+sqrt(2))=",sq2a,"^2=",mods(sq2a^2,n));
quit;
--------
mpenguin is offline   Reply With Quote