Good way to minimize factoring algoritm twice?

[HiddenWarrior]

Ok, 2^p-1 has divider q of form q=2kp+1. Let's remember the thread: http://www.mersenneforum.org/showthread.php?t=1804 (see about explanation of p periodicity). So, we first find LowT and HighT. I'll show Visual Basic code to explain it (easy to rewrite on other langs):

Dim LowT as long
Dim HighT as long
For LowT = 1 To 4
If (2 * LowT * P + 1) Mod 8 = 1 Then Exit For
Next
For HighT = 1 To 4
If (2 * HighT * P + 1) Mod 8 = 7 Then Exit For
Next

If we'll test this code for different P's we'll find that LowT and HighT is 1,3 or 4. To say more! One of this numbers is always 4 and the other one is 1 or 3!!!

Now we can modify our q: q=8*p*iteration+2*p*lowt+1 (or q=8*p*iteration+2*p*hight+1). Futher: 2^p-1=q1*q2 (if is not prime). We can check again and we'll find that q1 or q2 always contains LowT or HighT with the value 4!!! Therefore we can check only dividers that contain 4 (the value of LowT or HighT) inside them.

Result: we can check only for dividers of form q=8*p*iteration+8*p+1=8*p*(iteration+1)+1=8*p*I+1 (where I begins its run from 1).

Some samples:
2^11-1=23*89 (23 it is I=1 and LowT=1, 89 it is I=1 HighT=4!!!)
2^23-1=47*178481 (47 it is I=1 and LowT=1, 178481 it is I=969 HighT=4!!!)
2^29-1=233*1103*2089 (233 it is I=1 and HighT=4!!!, 1103 it is I=5 LowT=3, 2089 it is I=9 HighT=4!!!)
and so on...

[dsouza123]

That is equivalent to:
given q = 2kp+1 only when 2k is a multiple of 8 is it a potential factor of 2^p -1
so with k = 1,2,3,,5,6,7,,9,10,11 a factor wont be found.

k must be a multiple of 4, or when (k mod 4) = 0 and k >= 4

8, 2*4, 2^3, 4*2, 8*1
16, 2*8, 2^4, 4*4, 8*2
24, 2*12, 2^3*3, 4*6, 8*3
32, 2*16, 2^5, 4*8, 8*4
40, 2*20, 2^3*5, 4*10, 8*5
48, 2*24, 2^4*3, 4*12, 8*6
56, 2*28, 2^3*7, 4*14, 8*7
64, 2*32, 2^6, 4*16, 8*8
72, 2*36, 2^3*3^2, 4*20, 8*9

that implies the formula should be q=8kp+1 and only when (q mod 8) = 1
is it a potential factor.

Is the q=2kp+1 imprecise ? Allowing many values that can't be a factor.
Is the test of (q mod 8) = 1 or = 7 not correct should it be only (q mod 8) = 1 ?

[Maybeso]

Originally Posted by dsouza123

That is equivalent to:
given q = 2kp+1 only when 2k is a multiple of 8 is it a potential factor of 2^p -1
so with k = 1,2,3,,5,6,7,,9,10,11 a factor wont be found.

No, he is saying that when k is one of those numbers, the 2k for the other factor will be a multiple of 8. Because the product, Mp, must be == 7 mod 8.

Notice that for 2^11 -1, it is the higher factor, 89, that has 8| 2k. What this means is, if we restrict our search to 8kp+1, we can't stop at the square root - not that we are trial factoring anywhere near that now.

So, HiddenWarrior - because we are not doing a complete search, not even to the square root - we can only check the smaller of any factor pairs. If we skip any 7 mod 8 factors, we will be skipping the entire pair. Knowing that the other factor is 8kp+1 does us no good if we never look at it. And we wouldn't want to. It is easier to check every possible factor up to 100 bits, rather than checking 1/8th of all factors up to 20 million bits.

Although, .... you may have something here ...
Once we get beyond 64 bits, it might be worth it to check 8kp+1 up to 127 bits.
Hmm, how often is the smallest factor == 1 mod 8, and how often 7 mod 8?
Does it make sense to check either of these subsets to a higher bit level?

[Maybeso]

Originally Posted by Maybeso

Although, .... you may have something here ...
Once we get beyond 64 bits, it might be worth it to check 8kp+1 up to 127 bits.
Hmm, how often is the smallest factor == 1 mod 8, and how often 7 mod 8?
Does it make sense to check either of these subsets to a higher bit level?

I checked http://www.mersenneforum.org/lmh/factor.zip - the factors LMH has found for p > 79M. The ratio is:
41.13% == 1 (mod 8)
58.87% == 7 (mod 8)

So is this enough of a difference to justify a separate search to a higher bit level?

[HiddenWarrior]

Originally Posted by Maybeso

Notice that for 2^11 -1, it is the higher factor, 89, that has 8| 2k. What this means is, if we restrict our search to 8kp+1, we can't stop at the square root - not that we are trial factoring anywhere near that now.

Yes, in this case we have to do factoring to [(2^p-1)/2] to find this factor. We'll move twice faster but will miss factors that has form of 8*p*i+2*p+1 (7 mod 8). Maybe it's some reasons to implemet it on higher bits like from 70bit level.

Originally Posted by Maybeso

Hmm, how often is the smallest factor == 1 mod 8, and how often 7 mod 8?

I can calculate this rate for all know factors from 0M..500M today...

[nfortino]

Originally Posted by HiddenWarrior

Yes, in this case we have to do factoring to [(2^p-1)/2] to find this factor. We'll move twice faster but will miss factors that has form of 8*p*i+2*p+1 (7 mod 8). Maybe it's some reasons to implemet it on higher bits like from 70bit level.



I can calculate this rate for all know factors from 0M..500M today...

Be very careful using LMH>79.3M data. We know not all factors are found, and it is conceivable more 1 mod 8 factors are missed than 7 mod 8 factors.

[HiddenWarrior]

Ok! I'll do report for two ranges 0M..79.3M and 79.3M and 500M then

[HiddenWarrior]

It is 44.x% for (1 mod 8) and 55.y% for (7 mod 8)
But we get 1 mod 8 only by q1=8*p*i+1 and 7 mod 8 we get by q2=2p+1 mod 8 and q3=6*p+1 mod 8. I think it is faster to check only q1 dividers than both q2 and q3 and this percentage doesn't realy show the right situation...