Random observation

jnml · 2014-04-27, 17:31

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 // 
		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:

$ 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) = 23, ([{23 1}])
	GCD(623, 2^11-1) = 89, ([{89 1}])

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

n: 31
$

What am I looking at?

ewmayer · 2014-04-28, 00:20

Quote:

Originally Posted by jnml

What am I looking at?

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

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

jnml · 2014-04-28, 10:11

Quote:

Originally Posted by ewmayer

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

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

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

$\qquad A_{\text{i}+1} = A_{\text{i}}^2 \qquad \pmod {\qquad Mp}$

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

$\qquad A_{\text{i}+1} = A_{\text{i}}$ .

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

$\qquad A = \{0, \quad 1\}$ .

For lack of known to me terminology, let me call the solution $x$ to

$\qquad y \equiv x^2 \qquad \pmod {\qquad Mn}$

when

$\qquad y = x$

or

$\qquad y = -x$

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

Setup

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

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

Question 1 (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" ;-)

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

$\qquad r-1 = ma, \qquad r+1 = nb; \qquad (m, n \in \mathbb N)$ .

Q2: Is it like that always? If so, why?

O3: If the FP $f$ is other than 1, it has the form

$\qquad f = nc$

where $c$ is a non trivial divisor of Mp.

Q3: See Q2.

R.D. Silverman · 2014-04-28, 10:58

Quote:

Originally Posted by jnml

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

$\qquad A_{\text{i}+1} = A_{\text{i}}^2 \qquad \pmod {\qquad Mp}$

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

$\qquad A_{\text{i}+1} = A_{\text{i}}$ .

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

$\qquad A = \{0, \quad 1\}$ .

For lack of known to me terminology, let me call the solution $x$ to

$\qquad y \equiv x^2 \qquad \pmod {\qquad Mn}$

when

$\qquad y = x$

or

$\qquad y = -x$

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

Setup

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

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

Question 1 (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" ;-)

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

$\qquad r-1 = ma, \qquad r+1 = nb; \qquad (m, n \in \mathbb N)$ .

Q2: Is it like that always? If so, why?

O3: If the FP $f$ is other than 1, it has the form

$\qquad f = nc$

where $c$ is a non trivial divisor of Mp.

Q3: See Q2.

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

jnml · 2014-04-28, 12:24

Quote:

Originally Posted by jnml

For lack of known to me terminology, let me call the solution $x$ to

$\qquad y \equiv x^2 \qquad \pmod {\qquad Mn}$

when

$\qquad y = x$

or

$\qquad y = -x$

a "fixed point modular root" (FPR).

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 $x$ to

$\qquad y \equiv x^2 \qquad \pmod {\qquad Mn}$

when

$\qquad y = x$

or

$\qquad y = -x$

or

$\qquad y = 1$

of a FP $y$ a "fixed point modular root" (FPR).

----

Quote:

Originally Posted by R.D. Silverman

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

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.)

LaurV · 2014-04-28, 13:41

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²-2². 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)²-(59*2)²=649²-118² and taking the result mod n, you get 64²-1²=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]

R.D. Silverman · 2014-04-28, 19:24

Quote:

Originally Posted by jnml

<snip>

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

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

jnml · 2014-04-28, 19:33

Quote:

Originally Posted by R.D. Silverman

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

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

R.D. Silverman · 2014-04-28, 20:41

Quote:

Originally Posted by jnml

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

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.

jnml · 2014-04-28, 20:43

Quote:

Originally Posted by R.D. Silverman

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.

Fair deal! ;-)

2014-04-28, 13:41	#6
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 Posts	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^213. 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=913=(11-2)(11+2), or, applying elementary calculus, n=11²-2². 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=(5911)²-(592)²=649²-118² and taking the result mod n, you get 64²-1²=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] Last fiddled with by LaurV on 2014-04-28 at 14:00

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
random comments, random questions and thread titles made for Google	jasong	Lounge	46	2017-05-09 12:32
An observation	xilman	Lounge	1	2016-08-07 20:32
About random number (random seed) in Msieve	Greenk12	Factoring	1	2008-11-15 13:56
Mersenne Observation....	petrw1	Math	5	2008-11-04 20:27
Interesting observation	MooooMoo	Lounge	15	2006-11-14 03:40