20140427, 17:31  #1 
Feb 2012
Prague, Czech Republ
164_{10} 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)<<n  1 for i := uint64(2); i <= mn2; i++ { k := i * i % mn // switch { case k == 1: fmt.Printf("%d^2 == %d (mod 2^%d1)\n", i, k, n) gcd := mathutil.GCDUint64(i1, mn) fmt.Printf("\tGCD(%d, 2^%d1) = %d, (%v)\n", i1, n, gcd, mathutil.FactorInt(uint32(gcd))) gcd = mathutil.GCDUint64(i+1, mn) fmt.Printf("\tGCD(%d, 2^%d1) = %d, (%v)\n\n", i+1, n, gcd, mathutil.FactorInt(uint32(gcd))) case k == i: fmt.Printf("%d^2 == %d (mod 2^%d1) (%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^111) GCD(621, 2^111) = 23, ([{23 1}]) GCD(623, 2^111) = 89, ([{89 1}]) 713^2 == 713 (mod 2^111) ([{23 1} {31 1}]) 1335^2 == 1335 (mod 2^111) ([{3 1} {5 1} {89 1}]) 1425^2 == 1 (mod 2^111) GCD(1424, 2^111) = 89, ([{89 1}]) GCD(1426, 2^111) = 23, ([{23 1}]) n: 13 n: 17 n: 19 n: 23 2677215^2 == 2677215 (mod 2^231) ([{3 1} {5 1} {178481 1}]) 3034178^2 == 1 (mod 2^231) GCD(3034177, 2^231) = 178481, ([{178481 1}]) GCD(3034179, 2^231) = 47, ([{47 1}]) 5354429^2 == 1 (mod 2^231) GCD(5354428, 2^231) = 47, ([{47 1}]) GCD(5354430, 2^231) = 178481, ([{178481 1}]) 5711393^2 == 5711393 (mod 2^231) ([{47 1} {137 1} {887 1}]) n: 29 61936760^2 == 1 (mod 2^291) GCD(61936759, 2^291) = 256999, ([{233 1} {1103 1}]) GCD(61936761, 2^291) = 2089, ([{2089 1}]) 66682969^2 == 66682969 (mod 2^291) ([{137 1} {233 1} {2089 1}]) 71429178^2 == 1 (mod 2^291) GCD(71429177, 2^291) = 2304167, ([{1103 1} {2089 1}]) GCD(71429179, 2^291) = 233, ([{233 1}]) 133365937^2 == 1 (mod 2^291) GCD(133365936, 2^291) = 1103, ([{1103 1}]) GCD(133365938, 2^291) = 486737, ([{233 1} {2089 1}]) 232720867^2 == 232720867 (mod 2^291) ([{101 1} {1103 1} {2089 1}]) 237467076^2 == 237467076 (mod 2^291) ([{2 2} {3 1} {7 1} {11 1} {233 1} {1103 1}]) 299403836^2 == 299403836 (mod 2^291) ([{2 2} {2089 1} {35831 1}]) 304150045^2 == 304150045 (mod 2^291) ([{5 1} {23 1} {233 1} {11351 1}]) 403504974^2 == 1 (mod 2^291) GCD(403504973, 2^291) = 486737, ([{233 1} {2089 1}]) GCD(403504975, 2^291) = 1103, ([{1103 1}]) 465441733^2 == 1 (mod 2^291) GCD(465441732, 2^291) = 233, ([{233 1}]) GCD(465441734, 2^291) = 2304167, ([{1103 1} {2089 1}]) 470187943^2 == 470187943 (mod 2^291) ([{31 1} {1103 1} {13751 1}]) 474934151^2 == 1 (mod 2^291) GCD(474934150, 2^291) = 2089, ([{2089 1}]) GCD(474934152, 2^291) = 256999, ([{233 1} {1103 1}]) n: 31 $ 
20140428, 00:20  #2 
∂^{2}ω=0
Sep 2002
República de California
9796_{10} Posts 
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 20140428 at 00:20 
20140428, 10:11  #3  
Feb 2012
Prague, Czech Republ
2^{2}·41 Posts 
Quote:
I was looking at sequences for different values. The sequence eventually forms a cycle, some of which can have only 1 item, ie. . For lack of known to me terminology let me call such A a "fixed point". The trivial FPs are . For lack of known to me terminology, let me call the solution to when or a "fixed point modular root" (FPR). From now on the trivial FPRs are not considered anymore. Setup Due to the exponentially growing running time of the naive program in the OP, only 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 iffish then the converse is also "interesting" ;) O2: If the FP is 1, its FPR is and are distinct non trivial divisors of Mp (ie. not 1 and not Mn) then . Q2: Is it like that always? If so, why? O3: If the FP is other than 1, it has the form where is a non trivial divisor of Mp. Q3: See Q2. 

20140428, 10:58  #4  
Nov 2003
2^{6}·113 Posts 
Quote:
"Lagrange's Theorem". 

20140428, 12:24  #5  
Feb 2012
Prague, Czech Republ
2^{2}·41 Posts 
Quote:
 For lack of known to me terminology, let me call the solution to when or or of a FP a "fixed point modular root" (FPR).  Quote:
(Would you meanwhile perhaps want to comment further on the questions in a bit more detail, it'll be appreciated very much.) 

20140428, 13:41  #6 
Romulan Interpreter
Jun 2011
Thailand
2^{2}×7×317 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^21=0, or (x1)(x+1)=0. From which both parenthesis contain nontrivial factors of n. Finding nontrivial 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 semisum and semidifference of them: (9+13)/2=11, (139)/2=2. So, you can write the product n=9*13=(112)(11+2), or, applying elementary calculus, n=11^{2}2^{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)^{2}(59*2)^{2}=649^{2}118^{2} and taking the result mod n, you get 64^{2}1^{2}=0 (mod 117), or (641)(64+1)=0. You just found a nontrivial 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 20140428 at 14:00 
20140428, 19:24  #7 
Nov 2003
2^{6}×113 Posts 

20140428, 19:33  #8 
Feb 2012
Prague, Czech Republ
2^{2}×41 Posts 

20140428, 20:41  #9 
Nov 2003
1C40_{16} Posts 

20140428, 20:43  #10 
Feb 2012
Prague, Czech Republ
2^{2}·41 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
random comments, random questions and thread titles made for Google  jasong  Lounge  46  20170509 12:32 
An observation  xilman  Lounge  1  20160807 20:32 
About random number (random seed) in Msieve  Greenk12  Factoring  1  20081115 13:56 
Mersenne Observation....  petrw1  Math  5  20081104 20:27 
Interesting observation  MooooMoo  Lounge  15  20061114 03:40 