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

alpertron · 2005-08-19, 17:07

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-19, 17:07	#8
alpertron Aug 2002 Buenos Aires, Argentina 3²×149 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=(Ii22modinv((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).