mersenneforum.org - View Single Post - Closed form solution of x^2 = 2 mod Fermat number

alpertron · 2005-08-18, 14:35

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 F_n). This would allow to factor F_n and you will appear in math books :-) .

2005-08-18, 14:35	#2
alpertron Aug 2002 Buenos Aires, Argentina 2476₈ 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=(Ii22modinv((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 F_n). This would allow to factor F_n and you will appear in math books :-) .