mersenneforum.org Closed form solution of x^2 = 2 mod Fermat number
 Register FAQ Search Today's Posts Mark Forums Read

 2005-08-18, 12:18 #1 mpenguin   Aug 2005 F16 Posts 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; --------
 2005-08-18, 14:35 #2 alpertron     Aug 2002 Buenos Aires, Argentina 23×3×5×11 Posts sqrt(2) mod F_n in UBASIC I translated the sqrt(2) program to UBASIC Code:  10 input N0 20 N=2^(2^N0)+1 30 Ii=modpow(2,2^(N0-1),N) 40 Ii2=modpow(2,2^(N0-2),N) 50 Sq2=(Ii2*2*modinv((1+Ii),N))@N 60 print Sq2,Sq2^2@N This is interesting, but it would be far more interesting to find another sqrt(2) that is not the negative of this one (mod Fn). This would allow to factor Fn and you will appear in math books :-) .
 2005-08-18, 14:49 #3 alpertron     Aug 2002 Buenos Aires, Argentina 23·3·5·11 Posts Unfortunately with the following code: Code: 10 input N0 20 N=2^(2^N0)+1 30 Ii=modpow(2,2^(N0-1),N) 40 Ii2=modpow(2,2^(N0-2),N) 50 Ii3=modpow(2,2^(N0-3),N) 60 Sq2=(Ii2*2*modinv((1+Ii),N))@N 70 Sq2a=(Ii3*2*modinv((Ii*Sq2+1-Ii),N)@N) 80 print Sq2,Sq2^2@N 90 print ((Sq2a*Sq2a)-2)@N I found that the values of sqrt(2) generated by calculating directly the sqrt(2) and calculating B=sqrt(2+sqrt(2)) and then B^2-2 = sqrt(2) are the same, so they cannot be used to factor Fn.
 2005-08-18, 15:23 #4 mpenguin   Aug 2005 3·5 Posts I am theory lamer, but according to wikipedia: >Let n ≥ 3 be a positive odd integer. Then n is a Fermat prime if and only if for every a >coprime to n, a is a primitive root mod n if and only if a is a quadratic nonresidue mod >n. Looks like sqrt(2) is not primitive root, so showing that it is nonresidue shows compositeness of Fn ? The original program computes sq2a^2 = 2+sqrt(2)=sqrt(2)*(1+sqrt(2)) (at least in C) so showing that any of sqrt(2),1+sqrt(2),1-sqrt(2) is nonresidue shows compositeness of Fn? The above reasoning may be quite buggy :)
 2005-08-18, 16:14 #5 mpenguin   Aug 2005 178 Posts When one takes the smaller absolute value of sq2 and sq2a ("signed mod") they have strange factorizations F[n] | sq2[n+i] and F[n] | sq2a[n+j].
 2005-08-18, 16:47 #6 alpertron     Aug 2002 Buenos Aires, Argentina 52816 Posts Using n=5, F5 = 4294967297. With your method you find sqrt(2) = 4278190337. If you somehow find sqrt(2) = 1370209359, you will be able to factor F5 since gcd(F5, 4278190337 - 1370209359) = 6700417 which is a proper factor of the original number.
 2005-08-19, 16:05 #7 mpenguin   Aug 2005 3×5 Posts sqrt(2) follows from: fn(n) = fn(n-1)^2-2*(fn(n-2)-1)^2 fn(n) is the nth Fermat number
 2005-08-19, 17:07 #8 alpertron     Aug 2002 Buenos Aires, Argentina 101001010002 Posts The code for sqrt(2) in UBASIC using your last post is: Code: 10 input N0 20 N=2^(2^N0)+1 30 Ii=2^(2^(N0-1)) 40 Ii2=2^(2^(N0-2)) 50 Sq2=(Ii2*2*modinv((1+Ii),N))@N 60 print Sq2,Sq2^2@N 70 print (Ii+1)*modinv(Ii2,N)@N Obviously both values of sqrt(2) are the same, since if the number computed in line 70 is B, the line 50 computes 2/B (mod N).
 2005-08-21, 16:11 #9 mpenguin   Aug 2005 3×5 Posts sqrt(2+sqrt(2+sqrt(2+sqrt(2+....sqrt(2))) are computable from Z and iterating x -> x^2 -2 may reach zero in n+1 steps. mupad code: Code: fn:=proc(n) begin 2^(2^n)+1;end_proc; n0:=7; n:=fn(n0); sq2:=mods(fn(n0-1)/(fn(n0-2)-1),n); mods(sq2^2,n); vk:=(fn(n0-2)/(2^(2^(n0-3)))); print(" ^2 -sq2[-1] ",1,mods(vk,n),mods(vk^2,n)-sq2); for i from 2 to n0-2 do vt:=sqrt(vk+2); print(" ^2 -sq2[-1] ",i,vt,mods(vt,n),mods(vk,n),mods(vt^2,n), "== 2, ",mods(vt^2-vk,n)); vk:=vt; end_for; s1:=mods(3*sq2/2,n); print(" + ",i,mods(s1,n),mods(vk,n),mods(s1^2-vk,n)); for i from 1 to n0+1 do print(" x -> x^2-2 ",i,gcd(s1,n),s1); s1:=mods(s1^2-2,n); end_for; quit;
 2005-09-28, 17:53 #10 Yamato     Sep 2005 Berlin 4216 Posts Let F(n) = 2^(2^n) + 1. Then the "trivial" square root of 2 is sqrt(2) = F(n-1) * inv(F(n-2) - 1) (mod F(n)) (inv is the inverse number mod F(n)) because of the real factorization F(n) = F(n-1)^2 - x^2 where x = (F(n-2) - 1)*sqrt(2)
2005-09-29, 07:46   #11
mpenguin

Aug 2005

11112 Posts

Quote:
 Originally Posted by Yamato Let F(n) = 2^(2^n) + 1. Then the "trivial" square root of 2 is

Yes, the square root of 2 is trivial mod Fn.

(2+2^(1/2))^2 and (2+(2+2^(1/2))^(1/2))^(1/2) mod Fn are a little more subtle.

 Similar Threads Thread Thread Starter Forum Replies Last Post michael Math 31 2015-09-04 05:57 literka Miscellaneous Math 73 2013-11-17 10:33 Batalov Miscellaneous Math 3 2013-11-06 19:01 Raman Math 1 2012-09-12 13:21 literka Factoring 5 2012-01-30 12:28

All times are UTC. The time now is 04:54.

Fri Aug 7 04:54:24 UTC 2020 up 21 days, 41 mins, 1 user, load averages: 1.75, 1.89, 1.88