mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2020-08-03, 17:30   #12
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

52·7 Posts
Default

It is perhaps also interesting to note the lengths of the "pre-periods", 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^p-1);S=s;for(i=1,t,S=S^2-2);i=0;while(s!=S,s=s^2-2;S=S^2-2;i++);i
Pass the Mersenne exponent as p, and the period length (from Batalov's post; of course Batalov's technique for finding the period length is also easy to write in PARI/GP) as t. In the function, the S sequence is always t positions ahead of the s sequence, so we just check to see how long it takes until they agree.

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
The last one, findOffset(59,345603421440), would take a long time with PARI/GP with this approach.

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
JeppeSN is offline   Reply With Quote
Old 2020-08-03, 18:13   #13
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

52×7 Posts
Default

Quote:
Originally Posted by Batalov View Post
Periods may (?) be different if we use the other popular seed values S0 = 10, or S0 = 2/3 (mod Mp).
That is true: This PARI/GP function imitates your program, with an optional seed argument:
Code:
findPeriod(p,seed=4)=s=Mod(seed,2^p-1);for(i=1,120000,s=s^2-2);S=s;i=0;until(s==S,S=S^2-2;i++);i
Results:
Code:
findPeriod(11)
60

findPeriod(11,10)
10

findPeriod(11,2/3)
5
So they do differ. The one for 2/3 is not even a multiple of 11 - 1 = 10. You may think PARI handles 2/3 wrong, but it does not: Evaluating findPeriod(11,683) also gives 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
JeppeSN is offline   Reply With Quote
Old 2020-08-03, 18:15   #14
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

961810 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.
Batalov is offline   Reply With Quote
Old 2020-10-01, 22:15   #15
jshort
 
"James Short"
Mar 2019
Canada

17 Posts
Default

Let S_{1} = 4 = (2 + \sqrt{3}) + (2 - \sqrt{3}) and S_{n+1} = S_{n}^{2} - 2.

We'll first prove via induction that S_{n} = (2 + \sqrt{3})^{2^{n-1}} + (2 - \sqrt{3})^{2^{n-1}}.

Clearly S_{1} = (2 + \sqrt{3})^{2^{1-1}} + (2 - \sqrt{3})^{2^{1-1} = (2 + \sqrt{3}) + (2 - \sqrt{3}) = 4. Assume that it holds for all k < m.

Now S_{m} = S_{m-1}^{2} - 2 = ((2 + \sqrt{3})^{2^{m-2}} + (2 - \sqrt{3})^{2^{m-2}})^{2} - 2 = (2 + \sqrt{3})^{2^{m-1}} + (2 - \sqrt{3})^{2^{m-1}} + 2(2 + \sqrt{3})^{2^{m-2}} \cdot (2 - \sqrt{3})^{2^{m-2}} - 2 = (2 + \sqrt{3})^{2^{m-1}} + (2 - \sqrt{3})^{2^{m-1}} + 2 - 2 = (2 + \sqrt{3})^{2^{m-1}} + (2 - \sqrt{3})^{2^{m-1}}

Note that in the above, I used the fact that (2 + \sqrt{3}) \cdot (2 - \sqrt{3}) = 1. Their inverses. Since their inverses of each other, they also have the same order over M_{p}.

Suppose the order of 2 + \sqrt{3} is n = 2^{i} \cdot m. If i=0, the order is odd. In any case, I believe n will have to be a factor of  \prod_{i} (p_{i}^{2} - 1) where p_{i} are the prime factors of M_{P}.**

First assume that n is odd.

Let r be the smallest integer such that 2^{r} \equiv 1 mod(n) In this case, we have that (2 + \sqrt{3})^{2^{r} - 1} \equiv 1 or (2 + \sqrt{3})^{2^{r}} \equiv 2 + \sqrt{3} .

The same can be repeated with 2 - \sqrt{3}. The result is that S_{r+1} = (2 + \sqrt{3})^{2^{r}} + (2 - \sqrt{3})^{2^{r}} \equiv (2 + \sqrt{3}) + (2 - \sqrt{3}) \equiv 4 \equiv S_{1}.

However what if n is even?

In this case, i > 0 where n = 2^{i} \cdot m. We can repeat the procedure above, however we have to start at S_{i+1} and instead of asking ourselves what the order of 2 is, we're asking what the order of 2^{i} is over m.

.............................

**My guess that the order n needs to be a factor of  \prod_{i} (p_{i}^{2} - 1) is based on the assumption that the number of invertible elements a + b \sqrt{3} over Z_{p} is always going to be p^{2} - 1, however my memory of group theory is fuzzy, so someone might want to check this!

Last fiddled with by jshort on 2020-10-01 at 22:42
jshort is offline   Reply With Quote
Old 2020-10-20, 17:23   #16
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2×353 Posts
Default

Quote:
Originally Posted by Batalov View Post
Periods may (?) be different if we use the other popular seed values S0 = 10, or S0 = 2/3 (mod Mp).
Period values for starting value 10:
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*(p-1) property.

Last fiddled with by Viliam Furik on 2020-10-20 at 17:25
Viliam Furik is offline   Reply With Quote
Old 2020-10-20, 23:22   #17
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2·353 Posts
Default

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 P-1 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 = 2210 = 101102
3x = 32^4 * 32^2 * 32^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)/2k, 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.
Viliam Furik is offline   Reply With Quote
Old 2020-12-04, 19:47   #18
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

13028 Posts
Default

Quote:
Originally Posted by jshort View Post
...so someone might want to check this!
Periods for M23 do not divide the said product.
Viliam Furik is offline   Reply With Quote
Old 2020-12-06, 15:36   #19
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

11·467 Posts
Default

Quote:
Originally Posted by jshort View Post
<snip>
Suppose the order of 2 + \sqrt{3} is n = 2^{i} \cdot m. If i=0, the order is odd. In any case, I believe n will have to be a factor of  \prod_{i} (p_{i}^{2} - 1) where p_{i} are the prime factors of M_{P}.**

First assume that n is odd.
<snip>
Let u = Mod(2+x,x^2-3). Then u^2 - 4*u + 1 = 0. Let R = Z[u]. If p > 3 is prime, the multiplicative order n = n(p) of u in R/pR indeed divides p^2 - 1. In fact, because norm(u) = +1 we can say more:

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 2-power 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 2-power 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 2020-12-06 at 15:43 Reason: fignix optsy
Dr Sardonicus is offline   Reply With Quote
Old 2020-12-06, 16:05   #20
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2×353 Posts
Default

I guess that similar thing is also possible for PRP tests, right? If so, could you write a method to work it out?
Viliam Furik is offline   Reply With Quote
Old 2020-12-07, 15:04   #21
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

11×467 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
I guess that similar thing is also possible for PRP tests, right? If so, could you write a method to work it out?
Possible, sure. But it falls under "theoretically (perhaps) interesting, but computationally useless." A simple Fermat test is whether an-1 == 1 (mod n). If instead you want to determine the smallest i and j such that

a^2i+j == a^2i (mod n),

even assuming n is prime and a is a primitive root (mod n), 2^i is the 2-power factor of n-1, and j is the multiplicative order of 2 modulo the odd part of n-1. And to find that, you need to factor n-1 completely. And there are primality proofs that require only partial factorizations.
Dr Sardonicus is offline   Reply With Quote
Old 2020-12-08, 06:56   #22
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
the smallest i and j such that
I had to read that few times and didn't fully got it yet. Why do you need to find both? Only j would be enough. Yet, you still may not factor n after that (you can run in a trivial factor 1 or n).
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
question: decidability for quadratic residues modulo a composite LaurV Math 18 2017-09-16 14:47
2 holes in bizarre theorem about composite Mersenne Numbers wildrabbitt Math 120 2016-09-29 21:52
Use Pepin's Tests for proving primality of Mersenne numbers ? T.Rex Math 12 2016-04-03 22:27
Factoring highly composite Mersenne numbers philmoore Factoring 21 2004-11-18 20:00

All times are UTC. The time now is 08:11.


Mon Dec 6 08:11:27 UTC 2021 up 136 days, 2:40, 0 users, load averages: 1.38, 1.53, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.