Random observation
 

[CODE]
package main

import (
"flag"
"fmt"
"github.com/cznic/mathutil"
"log"
"strconv"
)

func main() {
flag.Parse()
n, err := strconv.ParseUint(flag.Arg(0), 0, 31)
if err != nil {
log.Fatal(err)
}

mn := uint64(1)<<n - 1
for i := uint64(2); i <= mn-2; i++ {
k := i * i % mn // [TEX]\qquad k = i^2 \quad \pmod {\quad M_n}[/TEX]
switch {
case k == 1:
fmt.Printf("%d^2 == %d (mod 2^%d-1)\n", i, k, n)
gcd := mathutil.GCDUint64(i-1, mn)
fmt.Printf("\tGCD(%d, 2^%d-1) = %d, (%v)\n", i-1, n, gcd, mathutil.FactorInt(uint32(gcd)))
gcd = mathutil.GCDUint64(i+1, mn)
fmt.Printf("\tGCD(%d, 2^%d-1) = %d, (%v)\n\n", i+1, n, gcd, mathutil.FactorInt(uint32(gcd)))
case k == i:
fmt.Printf("%d^2 == %d (mod 2^%d-1) (%v)\n\n", i, k, n, mathutil.FactorInt(uint32(i)))
}
}
}
[/CODE]

[CODE]
$ for n in 2 3 5 7 11 13 17 19 23 29 31 ; do echo n: $n ; ./20140425 $n ; done
n: 2
n: 3
n: 5
n: 7
n: 11
622^2 == 1 (mod 2^11-1)
GCD(621, 2^11-1) = [B]23[/B], ([{[B]23[/B] 1}])
GCD(623, 2^11-1) = [B]89[/B], ([{[B]89[/B] 1}])

713^2 == 713 (mod 2^11-1) ([{[B]23[/B] 1} {31 1}])

1335^2 == 1335 (mod 2^11-1) ([{3 1} {5 1} {[B]89[/B] 1}])

1425^2 == 1 (mod 2^11-1)
GCD(1424, 2^11-1) = [B]89[/B], ([{[B]89[/B] 1}])
GCD(1426, 2^11-1) = [B]23[/B], ([{[B]23[/B] 1}])

n: 13
n: 17
n: 19
n: 23
2677215^2 == 2677215 (mod 2^23-1) ([{3 1} {5 1} {[B]178481[/B] 1}])

3034178^2 == 1 (mod 2^23-1)
GCD(3034177, 2^23-1) = [B]178481[/B], ([{[B]178481[/B] 1}])
GCD(3034179, 2^23-1) = [B]47[/B], ([{[B]47[/B] 1}])

5354429^2 == 1 (mod 2^23-1)
GCD(5354428, 2^23-1) = [B]47[/B], ([{[B]47[/B] 1}])
GCD(5354430, 2^23-1) = [B]178481[/B], ([{[B]178481[/B] 1}])

5711393^2 == 5711393 (mod 2^23-1) ([{[B]47[/B] 1} {137 1} {887 1}])

n: 29
61936760^2 == 1 (mod 2^29-1)
GCD(61936759, 2^29-1) = 256999, ([{[B]233[/B] 1} {[B]1103[/B] 1}])
GCD(61936761, 2^29-1) = [B]2089[/B], ([{[B]2089[/B] 1}])

66682969^2 == 66682969 (mod 2^29-1) ([{137 1} {[B]233[/B] 1} {[B]2089[/B] 1}])

71429178^2 == 1 (mod 2^29-1)
GCD(71429177, 2^29-1) = 2304167, ([{[B]1103[/B] 1} {[B]2089[/B] 1}])
GCD(71429179, 2^29-1) = [B]233[/B], ([{[B]233[/B] 1}])

133365937^2 == 1 (mod 2^29-1)
GCD(133365936, 2^29-1) = [B]1103[/B], ([{[B]1103[/B] 1}])
GCD(133365938, 2^29-1) = 486737, ([{[B]233[/B] 1} {[B]2089[/B] 1}])

232720867^2 == 232720867 (mod 2^29-1) ([{101 1} {[B]1103[/B] 1} {[B]2089[/B] 1}])

237467076^2 == 237467076 (mod 2^29-1) ([{2 2} {3 1} {7 1} {11 1} {[B]233[/B] 1} {[B]1103[/B] 1}])

299403836^2 == 299403836 (mod 2^29-1) ([{2 2} {[B]2089[/B] 1} {35831 1}])

304150045^2 == 304150045 (mod 2^29-1) ([{5 1} {23 1} {[B]233[/B] 1} {11351 1}])

403504974^2 == 1 (mod 2^29-1)
GCD(403504973, 2^29-1) = 486737, ([{[B]233[/B] 1} {[B]2089[/B] 1}])
GCD(403504975, 2^29-1) = [B]1103[/B], ([{[B]1103[/B] 1}])

465441733^2 == 1 (mod 2^29-1)
GCD(465441732, 2^29-1) = [B]233[/B], ([{[B]233[/B] 1}])
GCD(465441734, 2^29-1) = 2304167, ([{[B]1103[/B] 1} {[B]2089[/B] 1}])

470187943^2 == 470187943 (mod 2^29-1) ([{31 1} {[B]1103[/B] 1} {13751 1}])

474934151^2 == 1 (mod 2^29-1)
GCD(474934150, 2^29-1) = [B]2089[/B], ([{[B]2089[/B] 1}])
GCD(474934152, 2^29-1) = 256999, ([{[B]233[/B] 1} {[B]1103[/B] 1}])

n: 31
$
[/CODE]
What am I looking at?

[QUOTE=jnml;372124]What am I looking at?[/QUOTE]

That's the same thing the rest of us are wondering.

Candidate for "world's worst factoring method", mayhap? You tell us.

[QUOTE=ewmayer;372146]That's the same thing the rest of us are wondering.

Candidate for "world's worst factoring method", mayhap? You tell us.[/QUOTE]

Sorry! Obviously I should have been more explicit as I didn't realize that someone can confuse it with a factorization method.

I was looking at sequences

[TEX]\qquad A_{\text{i}+1} = A_{\text{i}}^2 \qquad \pmod {\qquad Mp}[/TEX]

for different [TEX]A_1[/TEX] values. The sequence eventually forms a cycle, some of which can have only 1 item, ie.

[TEX]\qquad A_{\text{i}+1} = A_{\text{i}}[/TEX].

For lack of known to me terminology let me call such A a "fixed point". The trivial FPs are

[TEX]\qquad A = \{0, \quad 1\}[/TEX].

For lack of known to me terminology, let me call the solution [TEX]x[/TEX] to

[TEX]\qquad y \equiv x^2 \qquad \pmod {\qquad Mn}[/TEX]

when

[TEX]\qquad y = x[/TEX]

or

[TEX]\qquad y = -x[/TEX]

a "fixed point modular root" (FPR). From now on the trivial FPRs [TEX]\{-1, \quad 0, \quad 1\}[/TEX] are not considered anymore.

[U]Setup[/U]

Due to the exponentially growing running time of the naive program in the OP, only [TEX]M_{\text{p}}, \qquad p \leq 31[/TEX] were tested.

[U]Observation 1 [/U](O1): In the depicted limited test set, only composite Mps demonstrate non trivial FPRs.

[U]Question 1[/U] (Q1): Is that a coincidence or is that guaranteed? If so, what is the explanation/rule about it?

Note: If it is guaranteed then any proof a particular FPR exists is equal to a proof that such Mn is composite. If the relation is iff-ish then the converse is also "interesting" ;-)

[U]O2[/U]: If the FP is 1, its FPR is [TEX]r[/TEX] and [TEX]a, b[/TEX] are distinct non trivial divisors of Mp (ie. not 1 and not Mn) then

[TEX]\qquad r-1 = ma, \qquad r+1 = nb; \qquad (m, n \in \mathbb N)[/TEX].

[U]Q2[/U]: Is it like that always? If so, why?

[U]O3[/U]: If the FP [TEX]f[/TEX] is other than 1, it has the form

[TEX]\qquad f = nc[/TEX]

where [TEX]c[/TEX] is a non trivial divisor of Mp.

[U]Q3[/U]: See Q2.

[QUOTE=jnml;372171]Sorry! Obviously I should have been more explicit as I didn't realize that someone can confuse it with a factorization method.

I was looking at sequences

[TEX]\qquad A_{\text{i}+1} = A_{\text{i}}^2 \qquad \pmod {\qquad Mp}[/TEX]

for different [TEX]A_1[/TEX] values. The sequence eventually forms a cycle, some of which can have only 1 item, ie.

[TEX]\qquad A_{\text{i}+1} = A_{\text{i}}[/TEX].

For lack of known to me terminology let me call such A a "fixed point". The trivial FPs are

[TEX]\qquad A = \{0, \quad 1\}[/TEX].

For lack of known to me terminology, let me call the solution [TEX]x[/TEX] to

[TEX]\qquad y \equiv x^2 \qquad \pmod {\qquad Mn}[/TEX]

when

[TEX]\qquad y = x[/TEX]

or

[TEX]\qquad y = -x[/TEX]

a "fixed point modular root" (FPR). From now on the trivial FPRs [TEX]\{-1, \quad 0, \quad 1\}[/TEX] are not considered anymore.

[U]Setup[/U]

Due to the exponentially growing running time of the naive program in the OP, only [TEX]M_{\text{p}}, \qquad p \leq 31[/TEX] were tested.

[U]Observation 1 [/U](O1): In the depicted limited test set, only composite Mps demonstrate non trivial FPRs.

[U]Question 1[/U] (Q1): Is that a coincidence or is that guaranteed? If so, what is the explanation/rule about it?

Note: If it is guaranteed then any proof a particular FPR exists is equal to a proof that such Mn is composite. If the relation is iff-ish then the converse is also "interesting" ;-)

[U]O2[/U]: If the FP is 1, its FPR is [TEX]r[/TEX] and [TEX]a, b[/TEX] are distinct non trivial divisors of Mp (ie. not 1 and not Mn) then

[TEX]\qquad r-1 = ma, \qquad r+1 = nb; \qquad (m, n \in \mathbb N)[/TEX].

[U]Q2[/U]: Is it like that always? If so, why?

[U]O3[/U]: If the FP [TEX]f[/TEX] is other than 1, it has the form

[TEX]\qquad f = nc[/TEX]

where [TEX]c[/TEX] is a non trivial divisor of Mp.

[U]Q3[/U]: See Q2.[/QUOTE]

This is all trivial. Learn a little elementary group theory. Look up
"Lagrange's Theorem".

[QUOTE=jnml;372171]For lack of known to me terminology, let me call the solution [TEX]x[/TEX] to

[TEX]\qquad y \equiv x^2 \qquad \pmod {\qquad Mn}[/TEX]

when

[TEX]\qquad y = x[/TEX]

or

[TEX]\qquad y = -x[/TEX]

a "fixed point modular root" (FPR).
[/QUOTE]

Errata: It seems a case and condition was unfortunately dropped in the above quoted part. My apologies. I hope it's correct now.

----

For lack of known to me terminology, let me call the solution [TEX]x[/TEX] to

[TEX]\qquad y \equiv x^2 \qquad \pmod {\qquad Mn}[/TEX]

when

[TEX]\qquad y = x[/TEX]

or

[TEX]\qquad y = -x[/TEX]

or

[TEX]\qquad y = 1[/TEX]

of a FP [TEX]y[/TEX] a "fixed point modular root" (FPR).

----

[QUOTE=R.D. Silverman;372174]This is all trivial. Learn a little elementary group theory. Look up
"Lagrange's Theorem".[/QUOTE]

Thanks a lot! From the initial peeks at the relevant materials I found on the Internet, I guess it'll take me a [lot of | unbound] time to get through, but that's the exciting part about it.

(Would you meanwhile perhaps want to comment further on the questions in a bit more detail, it'll be appreciated very much.)

As said before, this is elementary algebra and it has nothing to do with mersenne numbers. All odd composites which are not a pure power of a single prime (i.e. they have at least 2 different primes in their factorization) have non trivial square roots of unity (easy to prove), i.e. there is a number x which is not 1, neither -1, such as x^2=1 (mod n). That is x^2-1=0, or (x-1)(x+1)=0. From which both parenthesis contain nontrivial factors of n. Finding non-trivial square roots of unity is equivalent with factorization of n.

Example: take the number n=117=3^2*13. Separate the factors in two disjunct groups (i.e. their gcd is 1). Here only 9 and 13 is possible. Take the semi-sum and semi-difference of them: (9+13)/2=11, (13-9)/2=2. So, you can write the product n=9*13=(11-2)(11+2), or, applying elementary calculus, n=11[SUP]2[/SUP]-2[SUP]2[/SUP]. Now, 2 is reversible mod 117 (why? can you prove for general case?) and its inverse is 1/2=59 (mod 117). Multiplying both terms of the equation with 1/4=59^2 you get 3481n=(59*11)[SUP]2[/SUP]-(59*2)[SUP]2[/SUP]=649[SUP]2[/SUP]-118[SUP]2[/SUP] and taking the result mod n, you get 64[SUP]2[/SUP]-1[SUP]2[/SUP]=0 (mod 117), or (64-1)(64+1)=0. You just found a non-trivial square root of unity modulo 117, which in our case is 64. Indeed, 64^2=1 (mod 117).

This calculus is reversible, if you know a nontrivial square root of unity, then you can easily factor n.

[edit: of course, reciprocal, when n is prime, its only square roots of unity mod n are 1 and -1, so yes, your "theory" is always guaranteed to hold. Now what is missing is that you come with an efficient (logarithmic) method to find square roots of unity mod n]

[QUOTE=jnml;372179]

<snip>

(Would you meanwhile perhaps want to comment further on the questions in a bit more detail, it'll be appreciated very much.)[/QUOTE]

A pointless exercize on my part; You lack the necessary math background.

[QUOTE=R.D. Silverman;372205]A pointless exercize on my part; You lack the necessary math background.[/QUOTE]

Is that assuming I cannot learn new things? ;-)

[QUOTE=jnml;372207]Is that assuming I cannot learn new things? ;-)[/QUOTE]

You wrote:

From the initial peeks at the relevant materials I found on the Internet, I guess it'll take me a [lot of | unbound] time to get through,

After you spend the time, we can talk.

[QUOTE=R.D. Silverman;372220]You wrote:

From the initial peeks at the relevant materials I found on the Internet, I guess it'll take me a [lot of | unbound] time to get through,

After you spend the time, we can talk.[/QUOTE]

Fair deal! ;-)