20200803, 17:30  #12 
"Jeppe"
Jan 2016
Denmark
5^{2}·7 Posts 
It is perhaps also interesting to note the lengths of the "preperiods", or offsets. That is the number of terms in the LL sequence preceding the first occurrence of the period. With Batalov's data as input, that is easy (PARI/GP):
Code:
findOffset(p,t)=s=Mod(4,2^p1);S=s;for(i=1,t,S=S^22);i=0;while(s!=S,s=s^22;S=S^22;i++);i Result: Code:
findOffset(11,60) 1 findOffset(23,32340) 1 findOffset(29,252) 1 findOffset(37,516924) 5 findOffset(41,822960) 1 findOffset(43,420) 3 findOffset(47,20338900) 4 findOffset(53,1309620) 2 Not sure if the above values have any interesting interpretation. We see that for the cases I was able to resolve, the constant 120000 in Batalov's C program was on the safe side. Of course, Viliam Furik's approach (searching for "14") works exactly in the cases where findOffset gives 1. /JeppeSN 
20200803, 18:13  #13  
"Jeppe"
Jan 2016
Denmark
5^{2}×7 Posts 
Quote:
Code:
findPeriod(p,seed=4)=s=Mod(seed,2^p1);for(i=1,120000,s=s^22);S=s;i=0;until(s==S,S=S^22;i++);i Code:
findPeriod(11) 60 findPeriod(11,10) 10 findPeriod(11,2/3) 5 Explicitly, the LL sequence for 2^11  1, starting from seed 2/3 == 683, is: 683 > 1818 > 1264 > 1034 > 620 > 1609 > 1471 > 160 > 1034 > etc. Similarly, for 2^29  1, and seed 2/3, the period length is 154, which is 14 mod 28. /JeppeSN 

20200803, 18:15  #14 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9618_{10} Posts 
You have a solid footing to retrace Tony's DiGraphs adventure, now! It is a bit of a déjà vu, but a good warm up to visit his old threads.

20201001, 22:15  #15 
"James Short"
Mar 2019
Canada
17 Posts 
Let and .
We'll first prove via induction that . Clearly . Assume that it holds for all . Now Note that in the above, I used the fact that . Their inverses. Since their inverses of each other, they also have the same order over . Suppose the order of is . If , the order is odd. In any case, I believe will have to be a factor of where are the prime factors of .** First assume that is odd. Let be the smallest integer such that In this case, we have that or . The same can be repeated with . The result is that . However what if is even? In this case, where . We can repeat the procedure above, however we have to start at and instead of asking ourselves what the order of is, we're asking what the order of is over . ............................. **My guess that the order needs to be a factor of is based on the assumption that the number of invertible elements over is always going to be , however my memory of group theory is fuzzy, so someone might want to check this! Last fiddled with by jshort on 20201001 at 22:42 
20201020, 17:23  #16  
"Viliam Furík"
Jul 2018
Martin, Slovakia
2×353 Posts 
Quote:
M11 > 10 (1 * 10) M23 > 32340 (1470 * 22) M29 > 252 (9 * 28) M37 > 516924 (14359 * 36) M41 > 822960 (20574 * 40) M43 > 420 (10 * 42) They are all the same (at least for these exponents) as with S(0) = 4, except for the M11. I have also looked at periods in PRP testing: M11 > 10 (1 * 10) M23 > 528 (24 * 22) M29 > 252 (9 * 28) M37 > 516924 (14359 * 36) M41 > x > 3077786 M43 > 9492 (226 * 42) Here they are more different. But still sometimes the same as for LL, and also preserve the k*(p1) property. Last fiddled with by Viliam Furik on 20201020 at 17:25 

20201020, 23:22  #17 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2·353 Posts 
I have done the PRP part because I realized that if we know the period of the PRP test of a composite exponent, we can run P1 in a different way (which may or may not be faster, probably not), by simply computing the product of primes * 2p, finding its binary representation, and multiplying residues corresponding to powers of 1s in the representation, modulo the period, and doing the GCD.
Of course, that only pays out if the period is smaller than the log2 of the (2p * product of primes smaller than smallest B1 needed ). It depends on the smoothness of the factors of Mp. EXAMPLE: p = 11 B1=1 E(B1) > product of all primes less than B1 x = E(1) * 2 * p = 22_{10} = 10110_{2} 3^{x} = 3^{2^4} * 3^{2^2} * 3^{2^1} (I compute the As all powers here are smaller than the period length, the method is of no use in this case. If there was a power of 3 higher than the period length + the length of the aperiodic part, then we can find a corresponding power of 3 that is less by some multiple of the period length. The obvious upper bound for the period is the number of quadratic residues, phi(Mp)/2^{k}, where k is the number of factors of Mp, and phi(n) is the Euler totient function. ................................... Because I realize that this method might never be possible to use, due to needed bound being much lower than necessary, I have been thinking about it for about 6 hours now. If you think it's unusable, you are most probably right. 
20201204, 19:47  #18 
"Viliam Furík"
Jul 2018
Martin, Slovakia
1302_{8} Posts 

20201206, 15:36  #19  
Feb 2017
Nowhere
11·467 Posts 
Quote:
If p > 3, then n(p) divides p  (12/p) = p  kronecker(12,p) = p  kronecker(3,p) which is p  1 if p is congruent to 1 or 11 (mod 12) and p + 1 if p is congruent to 5 or 7 (mod 12). The multiplicative order for powers of these primes, and for p = 2 and 3, are left as exercises for the reader. For a composite modulus N, the multiplicative order n(N) of u in R/NR is the lcm of the multiplicative orders modulo the prime (power) factors of N. What you want is different, however. You want to find i and j such that u^(2^(i+j)) == u^(2^i) (mod NR), which requires 2^(i+j) == 2^i (mod (n(N)), or 2^i*(2^j  1) == 0 (mod n(N)). Thus, the exponent i has to be at least as large as the exponent of the 2power factor of n(N), and j has to be divisible by the multiplicative order of 2 modulo the odd part of n(N). So if 2^i is the 2power factor of n(N), m = n(N)/2^i, and j is the multiplicative order of Mod(2, m), then the repetition of u^(2^k) starts at u^(2^i) and has period j. For N = 2^23  1 we find n(N) = 4105086 = 2*2052543, and znorder(Mod(2,2052543)) = 32340. With u1 = Mod(1, 2^23  1)*u we find that u1^(2^32340) =/= u1, but u1^(2^(2+32340)) == u1^2. Last fiddled with by Dr Sardonicus on 20201206 at 15:43 Reason: fignix optsy 

20201206, 16:05  #20 
"Viliam Furík"
Jul 2018
Martin, Slovakia
2×353 Posts 
I guess that similar thing is also possible for PRP tests, right? If so, could you write a method to work it out?

20201207, 15:04  #21  
Feb 2017
Nowhere
11×467 Posts 
Quote:
a^2^{i+j} == a^2^{i} (mod n), even assuming n is prime and a is a primitive root (mod n), 2^i is the 2power factor of n1, and j is the multiplicative order of 2 modulo the odd part of n1. And to find that, you need to factor n1 completely. And there are primality proofs that require only partial factorizations. 

20201208, 06:56  #22 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{4}·613 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring composite Mersenne numbers using Pollard Rho  jshort  Factoring  9  20190409 16:34 
question: decidability for quadratic residues modulo a composite  LaurV  Math  18  20170916 14:47 
2 holes in bizarre theorem about composite Mersenne Numbers  wildrabbitt  Math  120  20160929 21:52 
Use Pepin's Tests for proving primality of Mersenne numbers ?  T.Rex  Math  12  20160403 22:27 
Factoring highly composite Mersenne numbers  philmoore  Factoring  21  20041118 20:00 