x^2 = n mod Mn

[mpenguin]

Originally Posted by alpertron

Why?

What is the value of a?

By definition:
N=a^k-1;
For Mersenne numbers the value of "a" is 2.

Can't edit the original post, but t0=tanh(x/2);

So:
a=sinh(x)+cosh(x)=e^x
Let t0=tanh(x/2)
then:
rewrite(cos(I*x)+I*sin(I*x),exp)

exp(-x)=a
a^k=1, so we have t0 (and I*t0) which serves as something similar to tan(PI/k), but in Zn.

[mpenguin]

Originally Posted by R.D. Silverman

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.

Note that the algorithm does NOT find ARBITRARY square roots, just a square root of
+/- p mod 2^p-1

[R.D. Silverman]

Originally Posted by mpenguin

Note that the algorithm does NOT find ARBITRARY square roots, just a square root of
+/- p mod 2^p-1

Just one????

Find a second one and you will be famous.....

[alpertron]

Well, the same problem occurs on the thread http://www.mersenneforum.org/showthread.php?t=4516 where a square root of 2 modulo a Fermat number (which can be composite) is found. The problem is that we cannot find another non-trivial square root of 2.

[mpenguin]

Originally Posted by R.D. Silverman

Just one????

Find a second one and you will be famous.....

We don't care about fame much.

What surprised me that +/- p is guaranteed to be square residue (+ or - depending on p mod 4) for all p up to about 4000.

Is there an analytic explanation?

[R.D. Silverman]

Originally Posted by mpenguin

We don't care about fame much.

What surprised me that +/- p is guaranteed to be square residue (+ or - depending on p mod 4) for all p up to about 4000.

Is there an analytic explanation?

Hint: is -1 a q.r. or non q.r.?

Hint: if p is a non-residue what is -p?

[mpenguin]

The algorithm was extended to either solving

A)
x^2 = +/- k mod N
where
N=a^((2^m)*k)+1
or
N=a^((2^m)*k)-1
with k odd, + or - depending on k mod 4

or

B) finding factors of N and removing them solving A)

Some numerical experiments suggest that if solution is known to:

a^b=1 mod N, N not being of special form

a loop to (b-1)/2 may reveal a factor of N.

[akruppa]

Originally Posted by R.D. Silverman

Just one????

Find a second one and you will be famous.....

Oh, easy. If r is one square root of a (mod N), then N-r is a second one.

Woohoo, I'm famous!!

This probably isn't the answer you had been looking for, but we said we'd be super-duper-precise here in the math forum, didn't we?

Alex