mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-04-27, 17:31   #1
jnml
 
Feb 2012
Prague, Czech Republ

16410 Posts
Question 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 // \qquad k = i^2 \quad \pmod {\quad M_n}
		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?
jnml is offline   Reply With Quote
Old 2014-04-28, 00:20   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

979610 Posts
Default

Quote:
Originally Posted by jnml View Post
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.

Last fiddled with by ewmayer on 2014-04-28 at 00:20
ewmayer is online now   Reply With Quote
Old 2014-04-28, 10:11   #3
jnml
 
Feb 2012
Prague, Czech Republ

22·41 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
jnml is offline   Reply With Quote
Old 2014-04-28, 10:58   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by jnml View Post
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".
R.D. Silverman is offline   Reply With Quote
Old 2014-04-28, 12:24   #5
jnml
 
Feb 2012
Prague, Czech Republ

22·41 Posts
Default

Quote:
Originally Posted by jnml View Post
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 View Post
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.)
jnml is offline   Reply With Quote
Old 2014-04-28, 13:41   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×317 Posts
Default

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=112-22. 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)2-(59*2)2=6492-1182 and taking the result mod n, you get 642-12=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
LaurV is offline   Reply With Quote
Old 2014-04-28, 19:24   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by jnml View Post

<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.
R.D. Silverman is offline   Reply With Quote
Old 2014-04-28, 19:33   #8
jnml
 
Feb 2012
Prague, Czech Republ

22×41 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
A pointless exercize on my part; You lack the necessary math background.
Is that assuming I cannot learn new things? ;-)
jnml is offline   Reply With Quote
Old 2014-04-28, 20:41   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by jnml View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2014-04-28, 20:43   #10
jnml
 
Feb 2012
Prague, Czech Republ

22·41 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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! ;-)
jnml is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:52.

Thu Oct 29 23:52:13 UTC 2020 up 49 days, 21:03, 1 user, load averages: 1.94, 1.98, 1.98

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.