mersenneforum.org Random observation
 Register FAQ Search Today's Posts Mark Forums Read

 2014-04-27, 17:31 #1 jnml   Feb 2012 Prague, Czech Republ A916 Posts 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)<
2014-04-28, 00:20   #2
ewmayer
2ω=0

Sep 2002
República de California

2·3·1,931 Posts

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.

Last fiddled with by ewmayer on 2014-04-28 at 00:20

2014-04-28, 10:11   #3
jnml

Feb 2012
Prague, Czech Republ

101010012 Posts

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.

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

Nov 2003

22×5×373 Posts

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

2014-04-28, 12:24   #5
jnml

Feb 2012
Prague, Czech Republ

132 Posts

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

 2014-04-28, 13:41 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 100011110010012 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^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
2014-04-28, 19:24   #7
R.D. Silverman

Nov 2003

746010 Posts

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

2014-04-28, 19:33   #8
jnml

Feb 2012
Prague, Czech Republ

132 Posts

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? ;-)

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

Nov 2003

22·5·373 Posts

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.

2014-04-28, 20:43   #10
jnml

Feb 2012
Prague, Czech Republ

132 Posts

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! ;-)

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Lounge 46 2017-05-09 12:32 xilman Lounge 1 2016-08-07 20:32 Greenk12 Factoring 1 2008-11-15 13:56 petrw1 Math 5 2008-11-04 20:27 MooooMoo Lounge 15 2006-11-14 03:40

All times are UTC. The time now is 15:49.

Tue Jan 26 15:49:44 UTC 2021 up 54 days, 12:01, 0 users, load averages: 1.92, 2.49, 2.70