 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 3×5 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 138510 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 5·277 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 101011010012 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 5×277 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 1028 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

3·5 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.  Thread Tools Show Printable Version Email this Page 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 08:36.

Mon Nov 29 08:36:01 UTC 2021 up 129 days, 3:05, 0 users, load averages: 1.59, 1.35, 1.22