mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   Repeating residues in LL tests of composite Mersenne numbers (https://www.mersenneforum.org/showthread.php?t=25772)

 Viliam Furik 2020-07-24 20:10

Repeating residues in LL tests of composite Mersenne numbers

I have noticed, that when doing LL tests far behind the p-2 iteration, residues start to repeat with a certain period. This happens only for composite Mersenne numbers because when prime ones hit 0, next iteration yields 2^p-2, and then the residue is 2 all the way up to infinity.

I found periods for four composite Mersenne numbers, using my rather slow Python script:

M11 - 60 iters
M23 - 32340 iters
M29 - 252 iters
M37 - ??? iters (did not finish in my patience time)
M41 - 822960 iters

I wonder what's the reason behind these periods. Is there some formula for them? Can this be used somehow for testing or factoring purposes? Is it even known fact?

My best guess is that it's the number of quadratic residues modulo Mersenne number.

 Viliam Furik 2020-07-25 10:00

[QUOTE=Viliam Furik;551475]...when prime ones hit 0, next iteration yields 2^p-2, and then the residue is 2...
[/QUOTE]
It should be 2^p - 3, or Mp - 2.

 preda 2020-08-01 07:52

[QUOTE=Viliam Furik;551475]I have noticed, that when doing LL tests far behind the p-2 iteration, residues start to repeat with a certain period. This happens only for composite Mersenne numbers because when prime ones hit 0, next iteration yields 2^p-2, and then the residue is 2 all the way up to infinity.

I found periods for four composite Mersenne numbers, using my rather slow Python script:

M11 - 60 iters
M23 - 32340 iters
M29 - 252 iters
M37 - ??? iters (did not finish in my patience time)
M41 - 822960 iters

I wonder what's the reason behind these periods. Is there some formula for them? Can this be used somehow for testing or factoring purposes? Is it even known fact?

My best guess is that it's the number of quadratic residues modulo Mersenne number.[/QUOTE]

Hi Viliam, I'm by no means an LL expert, and I don't have an answer to your question here. However, I would approach the question by drilling down into one (or a few) mathematical proofs of the LL test, to understand why it works and the underlying mechanics. Might be that what we see is the "multiplicative order" in some group on which LL is based.. anyway somebody more maths-grounded could probably easily shed light here.

 JeppeSN 2020-08-02 09:26

The LL sequence starts 4, 14, 194, ...

Since we calculate modulo 2^p - 1, there are only finitely many values we can hit, so sooner or later we are going to hit a value we have seen before.

For 2^p - 1 prime, we know we hit 0, "-2", 2, 2, 2, ... So the period starts late and has length 1.

For 2^p - 1 composite (p prime), do you know if it is always 14 which is the first term to reappear? How does your script detect that a period has finished (in order to report the period length)?

/JeppeSN

 Viliam Furik 2020-08-02 12:50

[QUOTE=JeppeSN;552287]
For 2^p - 1 composite (p prime), do you know if it is always 14 which is the first term to reappear? How does your script detect that a period has finished (in order to report the period length)?

/JeppeSN[/QUOTE]

It simply looks for a value 14, based on previous observation, that periodicity starts at first modular squaring (S(1) = 14). But to answer previou question, I don't actually know that for sure, it's just that I haven't found a counterexample yet.

 Viliam Furik 2020-08-02 18:27

Python code

My slow but simple Python code in its entirity:
[CODE]s = 4
for a in range(2 ** 37 + 1):
s = (s ** 2 - 2) % (2 ** 37 - 1):
if s == 14:
print(a)[/CODE]

 Batalov 2020-08-02 23:47

[CODE] period 60 for M11
period 32340 for M23
period 252 for M29
period 516924 for M37
period 822960 for M41
period 420 for M43
period 20338900 for M47
period 1309620 for M53
period 345603421440 for M59

(period is always a multiple of (p-1) )
_____________

main(int argc,char **argv) {
uint64_t f,b,c,j,k,l,l2;
//...

if(argc<=1) { printf(" Use: %s p\n\t (copyleft) 2020 S.Batalov\n",argv[0]); exit(0); }
if(argc>1) l = atoll(argv[1]);
printf("# %lld ... testing\n",l);
l = 1ULL << l;
l--;
c = 4;
for(f=1; f<=120000;f++) { # or some other number, -- to get into "real" cycle
c = mulmod(c,c,l)-2;
}
b = c;
c = mulmod(b,b,l)-2;
for(f=1; c!=b && f<=l;f++) {
c = mulmod(c,c,l)-2;
}
printf(" period %lld for M%lld\n",f,atoll(argv[1]));
exit(0);
}
[/CODE]
The cycle does not include 4 (of course*), and not 14 or even 194 for larger p values, but we can greedily simply scroll forward "far enough".

*we all already know that we will never see 4 again, because 6 is a nonresidue. 16 and 196 are residues

 JeppeSN 2020-08-03 07:33

Thanks, Batalov, that confirms my suspicion. For example for p=37 (the first one Viliam Furik's method failed for), we start with:

4 -> 14 -> 194 -> 37634 -> 1416317954 -> (period starts here) 111419319480 -> ...

So in this case, the period starts at the first term after we have "wrapped around" because we work modulo 2^37 - 1 = 137438953471.

/JeppeSN

 Viliam Furik 2020-08-03 07:54

[QUOTE=Batalov;552363][CODE] period 60 for M11
period 32340 for M23
period 252 for M29
period 516924 for M37
period 822960 for M41
period 420 for M43
period 20338900 for M47
period 1309620 for M53
period 345603421440 for M59

(period is always a multiple of (p-1) )
[/CODE]
[/QUOTE]
Спасибо! But it still leaves the question "Why that period?" hanging in the air...

 Batalov 2020-08-03 08:35

We had a forum member about a decade ago who drilled into residue pathways/topology/cycles but he has left many years ago and left all that quite unfinished. (Tony "T.Rex")
He had some conjectures but as far as I remember those ended up broken.
(Including one about a Wagstaff number test.)

One can search forum way back, using Search / Advanced / Search by User Name, and search for his threads, such as DiGraph for LLT, LLT Cycles, LLT Tree... there is probably something of interest (just don't assume those things right ... or wrong), pick and chose what is useful.
...and more

 Batalov 2020-08-03 16:45

[QUOTE=Viliam Furik;552390]Спасибо! But it still leaves the question "Why that period?" hanging in the air...[/QUOTE]

Just a wild guess that:
1. residue is in effect a Chinese Remainder of residues mod all factors of these (composite) Mp
2. this is an lcm() of individual periods guided by each factor.

[CODE]M11 = 23 · 89
M23 = 47 · 178481
M29 = 233 · 1103 · 2089
M37 = 223 · 616318177
M41 = 13367 · 164511353
M43 = 431 · 9719 · 2099863
M47 = 2351 · 4513 · 13264529
M53 = 6361 · 69431 · 20394401
M59 = 179951 · 3203431780337[/CODE]
Factorizations are individual in each case (but each factor, as well known, has a multiple of (p+1) sitting in it, so this "reduced variety" reverberates through the process and helps lcm to be a multiple of (p-1) for one reason or another.

Periods may (?) be different if we use the other popular seed values S0 = 10, or S0 = 2/3 (mod Mp).

 JeppeSN 2020-08-03 17:30

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
[/CODE]
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
[/CODE]
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 2020-08-03 18:13

[QUOTE=Batalov;552444]Periods may (?) be different if we use the other popular seed values S0 = 10, or S0 = 2/3 (mod Mp).[/QUOTE]
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
[/CODE]
Results:
[CODE]findPeriod(11)
60

findPeriod(11,10)
10

findPeriod(11,2/3)
5
[/CODE]
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

 Batalov 2020-08-03 18:15

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.

 jshort 2020-10-01 22:15

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

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

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

Now [TEX]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}} [/TEX]

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

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

First assume that [TEX]n[/TEX] is odd.

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

The same can be repeated with [TEX]2 - \sqrt{3}[/TEX]. The result is that [TEX]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}[/TEX].

However what if [TEX]n[/TEX] is even?

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

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

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

 Viliam Furik 2020-10-20 17:23

[QUOTE=Batalov;552444]Periods may (?) be different if we use the other popular seed values S0 = 10, or S0 = 2/3 (mod Mp).[/QUOTE]

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.

 Viliam Furik 2020-10-20 23:22

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 = 22[SUB]10[/SUB] = 10110[SUB]2[/SUB]
3[SUP]x[/SUP] = 3[SUP]2^4[/SUP] * 3[SUP]2^2[/SUP] * 3[SUP]2^1[/SUP]
(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[SUP]k[/SUP], 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 2020-12-04 19:47

[QUOTE=jshort;558547]...so someone might want to check this![/QUOTE]

Periods for M23 do not divide the said product.

 Dr Sardonicus 2020-12-06 15:36

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

First assume that [TEX]n[/TEX] is odd.
<snip>[/QUOTE]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.

[b]What you want is different, however[/b]. 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.

 Viliam Furik 2020-12-06 16:05

I guess that similar thing is also possible for PRP tests, right? If so, could you write a method to work it out?

 Dr Sardonicus 2020-12-07 15:04

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

a^2[sup]i+j[/sup] == a^2[sup]i[/sup] (mod n),

[i]even assuming n is prime and a is a primitive root (mod n),[/i] 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 [i]that[/i], you need to factor n-1 [i]completely[/i]. And there are [i]primality proofs[/i] that require only partial factorizations.

 LaurV 2020-12-08 06:56

[QUOTE=Dr Sardonicus;565557]the smallest i and j such that
[/QUOTE]
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).

 Dr Sardonicus 2020-12-08 14:45

[QUOTE=LaurV;565631]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).[/QUOTE]I was merely trying to answer the question that had been asked.

In at least one case, things were so blindingly obvious it took me some time to see the answer. File this under [b][color=red]D'oh![/color][/b]

If N = 2^1277 - 1 (a composite M[sub]p[/sub]), then, as we know, N is a base-2 Fermat pseudoprime. But there is no need to factor N-1. It is trivial that the multiplicative order Mod(2, 2^1276 - 1) is 1276, and that therefore (with "a" any base to which

a[sup]N-1[/sup] == 1 (mod N), we have

a^(2^1277) == a^2 (mod N).

And you are absolutely right, this is of little to no help in factoring N. :tu:

 All times are UTC. The time now is 09:13.