mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-08-18, 12:18   #1
mpenguin
 
Aug 2005

3×5 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
Old 2005-08-18, 14:35   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×3×223 Posts
Default 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 :-) .
alpertron is offline   Reply With Quote
Old 2005-08-18, 14:49   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·3·223 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2005-08-18, 15:23   #4
mpenguin
 
Aug 2005

178 Posts
Default

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 :)
mpenguin is offline   Reply With Quote
Old 2005-08-18, 16:14   #5
mpenguin
 
Aug 2005

3×5 Posts
Default

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].
mpenguin is offline   Reply With Quote
Old 2005-08-18, 16:47   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·3·223 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2005-08-19, 16:05   #7
mpenguin
 
Aug 2005

3·5 Posts
Default

sqrt(2) follows from:
fn(n) = fn(n-1)^2-2*(fn(n-2)-1)^2

fn(n) is the nth Fermat number
mpenguin is offline   Reply With Quote
Old 2005-08-19, 17:07   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·3·223 Posts
Default

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).
alpertron is offline   Reply With Quote
Old 2005-08-21, 16:11   #9
mpenguin
 
Aug 2005

3×5 Posts
Default

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;
mpenguin is offline   Reply With Quote
Old 2005-09-28, 17:53   #10
Yamato
 
Yamato's Avatar
 
Sep 2005
Berlin

10000102 Posts
Default

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)
Yamato is offline   Reply With Quote
Old 2005-09-29, 07:46   #11
mpenguin
 
Aug 2005

3·5 Posts
Default

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.
mpenguin is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Special Form of Mersenne and Fermat Number Factors michael Math 31 2015-09-04 05:57
Number 59649589127497217 is a factor of Fermat number F7 literka Miscellaneous Math 73 2013-11-17 10:33
Another "solution for Fermat's Last Theorem" Batalov Miscellaneous Math 3 2013-11-06 19:01
Lucas-number prime factor form proofs Raman Math 1 2012-09-12 13:21
Fermat number F6=18446744073709551617 is a composite number. Proof. literka Factoring 5 2012-01-30 12:28

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

Thu Dec 3 04:30:48 UTC 2020 up 42 mins, 0 users, load averages: 1.02, 1.23, 1.21

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.