x^2 = n mod Mn

[mpenguin]

If Mn=2^n-1, n prime is there known efficient algorithm to compute:
x^2 = n mod Mn if n mod 4 =1
or
x^2 = -n mod Mn if n mod 4 = 3

(Mn is with unknown factorization).
?

Thanks.

[R.D. Silverman]

Originally Posted by mpenguin

If Mn=2^n-1, n prime is there known efficient algorithm to compute:
x^2 = n mod Mn if n mod 4 =1
or
x^2 = -n mod Mn if n mod 4 = 3

(Mn is with unknown factorization).
?

Thanks.

If P is a prime and P = 3 mod 4, then it is easy to see that

a^((p+1)/2) = sqrt(a) mod p.

Proof.

We have a^(P-1) = 1 mod P by Lagrange's Thm
--> a^P = a mod P
a^(P+1) = a^2 mod P
a^(P+1)/4 = a^(2/4) = a^(1/2) mod P

This requires that (P+1) be divisible by 4.

There is a similar result if P = 5 mod 8.

However, for P = +/- 1 mod 8, the best that is known is to apply
an algorithm such as Shanks/Tonelli. There is no simple 'formula'

[alpertron]

Originally Posted by R.D. Silverman

There is a similar result if P = 5 mod 8.

If we want to compute the value s such that s² = n (mod p) where p = 5 (mod 8) we have to compute first the intermediate value v:

v = (2N)^(P-5)/8 mod p

then the modular square root is:

s = ((2Nv²-1)NV) mod p

[mpenguin]

Originally Posted by alpertron

If we want to compute the value s such that s² = n (mod p) where p = 5 (mod 8) we have to compute first the intermediate value v:

v = (2N)^(P-5)/8 mod p

then the modular square root is:

s = ((2Nv²-1)NV) mod p

Actually i was asking about solving:

x^2 = 2969 mod (2^2969-1)

Code will follow.

[mpenguin]

There is an efficient solution to:

x^2 = k mod (a^k-1)
or
x^2 = -k mod (a^k-1)

with k odd.

The estimated running time is loop from 1 to (k-1)/2.

In some cases a factor of a^k-1 is found.

In case a factor is found, a solution may not be found.

Achieved by abuse of sine product in C.

Verified for mersenne numbers up to 3500.

/*(c) 2005
 *
 * This program is distributed under the terms of the GPL v2.
*/

/*
 *if u^n0 = 1 mod n,
 *returns x^2 = +/- n0 mod n
 *n0 odd
 *
 *exploits a little patched from C/R sine product mod n:
 *product(sin(i*PI/n0,i=1..(n0-1)/2))*2^(n0-1)/2 == n0^(1/2) mod n
 *
 * mupad code
*/

tanp:=proc(x,y) begin (x+y)/(1-x*y); end_proc;
si:=proc(x) begin 2*x/(1+x^2);end_proc;
modcompl:=proc(a,n) begin return(mods(Re(a),n)+I*mods(Im(a),n));end_proc;

mersroot2:=proc(u,n0,n)
local t0,ta,res,sq2,sq,i;
begin
if (powermod(u,n0,n)<>1) then return(0);end_if;
t0:=I*mods( (u-1)/(u+1),n);

res:=1;
ta:=0;
for i from 1 to (n0-1)/2 do
ta:=modcompl(tanp(ta,t0),n);
res:=modcompl(res*si(ta),n);
end_for;
sq2:=modcompl(res*(powermod(2,(n0-1)/2,n)),n);
return(sq2);
end_proc;

n0:=nextprime(3);
while (n0 < 100) do
n:=2^n0-1;
ro:=mersroot2(2,n0,n);
print(n0,mods(ro^2,n));
if (mods(ro^2,n)-n0 <> 0) then print("***bad***");end_if;
n0:=nextprime(n0+1);
end_while;

n:=nextprime(3);
n0:=5;
while (n < 100) do
if ((n-1) mod n0 = 0) then
pr:=numlib::primroot(n);
u:=powermod(pr,(n-1)/n0,n);
ro:=mersroot2(u,n0,n);
print(n,ro,mods(ro^2,n),numlib::isquadres(n0,n));
if (mods(ro^2,n)-n0 <> 0) then print("***bad***");end_if;
end_if;
n:=nextprime(n+1);
end_while;

/*
3^n0 -1 may be splitted
*/
u:=3;
n0:=31;
while (n0 < 517) do
n:=u^n0-1;
while ((n mod 2) = 0) do n:=n/2;end_while;
ro:=mersroot2(u,n0,n);
g1:=ro;
if (Re(g1) = 0) then g1:=Im(g1);end_if;
print(u,n0,ro,mods(ro^2,n),"gcd=",mods(gcd(g1,n),n));
if (mods(ro^2,n)-n0 <> 0) then print("***bad***");end_if;
n0:=n0+2;
end_while;

quit;

/*(c) 2005
 *
 * This program is distributed under the terms of the GPL v2.
 * maxima code
 *if u^n0 = 1 mod n,
 *returns x^2 = +/- n0 mod n
 *n0 odd
 *
 *exploits a little patched from C/R sine product mod n:
 *product(sin(i*PI/n0,i=1..(n0-1)/2))*2^(n0-1)/2 == n0^(1/2) mod n
 *
*/



inchar:%c___;
outchar:%d___;

tanp(x,y):=(x+y)/(1-x*y);
si(x):=2*x/(1+x^2);
modcompl(x,c):=MOD(REALPART(x),c)+%I*MOD(IMAGPART(x),c);
modpow(a,b,c):=block (
[x,y,z,d],
	x:a,
	y:b,
	z:1,
	DO ( 
	if (y = 0) then return(42),
		DO (
			if (MOD(y,2) # 0) then return(42),
			y:y/2,
			x:x*x,
			x:MOD(x,c)
		),
		y:y-1,
		z:z*x,
		z:MOD(z,c)
	),
z
);

mersroot2(u,n0,n):=block (
[t0,ta,res,sq2,sq,i],
	t0:%I*MOD( (u-1)/(u+1),n),
	res:1,
	ta:0,
	i:1,
	DO ( 
	if (i > (n0-1)/2) then return(42),
		ta:modcompl(tanp(ta,t0),n),
		res:modcompl(res*si(ta),n),
		i:i+1
	),
modcompl(res*(modpow(2,(n0-1)/2,n)),n)
);

n0:3;
lastn:100;
print(n0,lastn);
DO (
if (n0 > lastn) then return(42),
if (PRIMEP(n0)) then (
n:2^n0-1,
ro:mersroot2(2,n0,n),
print(n0,ro,MOD(ro^2,n)),
if ( MOD(ro^2-n0,n) # 0) then print("***bad***")
),
n0:n0+1
);
QUIT();

[R.D. Silverman]

Originally Posted by mpenguin

There is an efficient solution to:

x^2 = k mod (a^k-1)
or
x^2 = -k mod (a^k-1)

with k odd.

The estimated running time is loop from 1 to (k-1)/2.

In some cases a factor of a^k-1 is found.

Achieved by abuse of sine product in C.

Verified for mersenne numbers up to 3500.

Please don't post code. Post a description and analysis of the algorithm.
People generally don't have the time to extract the algorithm from the
code. I am curious about your method.

The Shanks/Tonelli algorithm is quite efficient for P = +/-1 mod 8.
But it is random.

[R.D. Silverman]

Originally Posted by R.D. Silverman

Please don't post code. Post a description and analysis of the algorithm.
People generally don't have the time to extract the algorithm from the
code. I am curious about your method.

The Shanks/Tonelli algorithm is quite efficient for P = +/-1 mod 8.
But it is random.

Yet another method [my preferred method] is to factor x^2 - a over GF(p)
via Cantor-Zassenhaus. This has the advantage in that it is more general;
one can factor x^d - a to get the d'th root. [when it exists]
It might be an interesting experiment to see which method is the fastest.
I suspect it will be strongly implementation and machine dependent.

In fact, this would be a terrific research project for any newbies with
good coding skills.

[alpertron]

Notice that the original poster is trying to find square roots modulo a composite number which is of the form 2^p - 1.

[mpenguin]

Originally Posted by R.D. Silverman

Please don't post code. Post a description and analysis of the algorithm.
People generally don't have the time to extract the algorithm from the
code. I am curious about your method.

The Shanks/Tonelli algorithm is quite efficient for P = +/-1 mod 8.
But it is random.

I believe my algorithm works for composite numbers with unknown factorization.

Will try to explain.

Lets try to do some trigonometry mod N. All variables mean tan(a/2) and are in Zn.

So some kind of "sine" very roughly speaking may be defined by:
si(x):=2*x/(1+x^2);
where x stands for tan(alpha/2), whatever alpha may be.

In traditional trigonometry the following seems to hold:

Product(k=1 to n-1) sin(PI*k/2n) = sqrt(n)/2^(n-1)

mod N the following seems to hold:

product(sin(i*PI/n0,i=1..(n0-1)/2))*2^(n0-1)/2 == n0^(1/2) mod n

(lower case i is not the imaginary unit, uppercase is in this notation).

By definition:

a^k=1

Let
a=cosh(x)+sinh(x)=e^x
Since a is known, so is tanh(alpha/2) so we are in Zn.
Let tanh(alpha/2)=t0.

Then I*t0 (I is just the usual symbol, not a number) gives a way to compute si(PI/k).
si(2*PI/k) is computed via adding tangens, si(3*PI/k) is adding it one more time and so on.

Actually all of the above may be completely wrong, that is why i posted reproducible code.

[alpertron]

Originally Posted by mpenguin

mod N the following seems to hold:

product(sin(i*PI/n0,i=1..(n0-1)/2))*2^(n0-1)/2 == n0^(1/2) mod n

Why?

Originally Posted by mpenguin

By definition:

a^k=1

Let
a=cosh(x)+sinh(x)=e^x
Since a is known, so is tanh(alpha/2) so we are in Zn.

What is the value of a?

[R.D. Silverman]

Originally Posted by alpertron

Notice that the original poster is trying to find square roots modulo a composite number which is of the form 2^p - 1.

Ah. I missed that.

Finding a square root modulo a composite is provably polynomial-time
equivalent to factoring. We can do one in polynomial time iff we can do
the other.

Thus, to efficiently find a square root of 2^p -1 requires knowing the
full factorization. Glory awaits anyone who can avoid this.