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

Yamato · 2005-09-28, 17:53

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-28, 17:53	#10
Yamato Sep 2005 Berlin 2×3×11 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)