Interesting observation re 2kp+1 numbers

[Fusion_power]

So take a mersenne number such as 2^17-1 which yields 131071

Find all the potential factors of form 2kp+1

1
35
69
103
137
171
205
239
273
307
341


Now divide the number by a 2kp value. Note the +1 is NOT used. 131071/340 = 385 with a remainder of 171. Anybody see something strange about that remainder? Lets do it again. 131071/204 = 642 with remainder 103. Anything ring bells yet?


Now I check the valid 2kp+1 values for 2^17-1 and find that 103, 137, 239, and 307 are the only valid 2kp+1 numbers and result from k values of 3, 4, 7, and 9. The mod results of testing these 4 numbers are: 1, 103, 171, and 103.

Fusion

[dsouza123]

What does

and find that 103, 137, 239, and 307 are the only valid 2kp+1 numbers

mean ?

In what sense are they valid and the others in the list (1..341) invalid ?

The mod results (131071 mod 2kp) had values (some duplicates) of 1, 35, 103, 171, 239 so if that has anything connection with the validity why is 137 in the valid list and 35,171 missing ?

131071 is prime anyway so only itself and 1 are factors.

Though there are more numbers 2kp+1 that goto 131071, 341 is the largest less than the square root of 131071.

[michael]

Fermat's little theorem gives:
2^p=2modp
2^p - 2=0modp
2^p - 2=2pm
2^p - 2=p(2k + 2k') (with m=k + k', choose k'<k)
2^p - 1=2pk + 2pk' + 1
2^p - 1mod(2kp)=2pk' + 1

So your observations are correct, every mersennenumber with prime exponent has a remainder of the form 2pk'+1 when you divide by 2kp.

-michael

[Fusion_power]

Dsouza,

Any potential factor of a Mp must be a prime number and not 3 or 5 mod 8. See http://www.utm.edu/research/primes/n...fs/MerDiv.html
and
http://www.mersenne.org/math.htm

Based on this you can eliminate 35 since it is divisible by 5, 171 is divisible by 3, etc.

This example is a very small Mp, so all are easily verified as prime or composite.

Fusion

[dsouza123]

Thanks for the explanation Fusion_power.

So the valid numbers are the 2kp+1 potential factors that are Prime and when mod 8 are not 3 and not 5.

I verified the numbers you listed, 307 even though it is prime, it is 3 when mod 8. So the list is a little shorter.

In the Prime95 help file under math it mentioned the valid factors are 1 or 7 mod 8.

I guess the quickest with the 2kp+1 is to mod by 8, if the result is 1 or 7 then test it (2kp+1) for primality.
At this point test it, using the powering algorithm or powmod or integer division with remainder.

If a 2kp+1 potential factor is 1 or 7 mod 8 and prime will it always be a true factor ?
Those two test are necessary (I believe) but are they sufficient ?

[Fusion_power]

Dsouza,

The sequence of verification is worth discussing. From a computational perspective, is it faster to determine if a number is prime or to determine if it is valid as 1 or 7 mod 8. From George's description, I think he first determines if a number is prime and then does the mod 8 verification. This might be faster if done the other way around.

Fusion

[ewmayer]

Originally posted by dsouza123
Thanks for the explanation Fusion_power.

So the valid numbers are the 2kp+1 potential factors that are Prime and when mod 8 are not 3 and not 5.

A recent thread about the special form or Mersenne and Fermat number factors is

http://www.mersenneforum.org/showthr...&threadid=1736

The fact that any factor q of M(p) must have from j*p+1 comes from some basic properties of multiplicative groups. The fact that the multiplier j must be even (i.e. j = 2*k) is a simple consequence of q having to be odd.

The q == +-1 mod 8 requirement comes from the theory of quadratic residues. Here's that argument:

From the form of N = 2^p - 1, we have that 2^p == 1 (mod N). Multiplying by 2, we see that 2^(p+1) == 2 (mod N). Since p is odd (primality of p is not crucial here, just oddness), the LHS is an even power of 2, hence a perfect square, which implies that 2 is a QR mod N, and thus also a QR mod any factor q of N. That immediately implies that q == +-1 (mod 8), i.e. that any factor q must be of the form 8*n +- 1. This does not change the form of k appearing in factors, but eliminates half of the k's that pass the multiple-of-small-prime sieve that is typically used in sieving programs.

If a 2kp+1 potential factor is 1 or 7 mod 8 and prime will it always be a true factor?

No. For small composite M(p) (i.e. where there is only a very small number of candidate factors satisfying the above requirements) it may happen to be true, but in general it isn't. For large p, since the number of potential q's grows exponentially with p but the average number of prime factors of M(p) grows very slowly (roughly as log(p)), the ratio of prime q's which are also factors of M(p) tends toward zero very rapidly. The reason sieving remains effective despite this is that the smallest factor of M(p) has a roughly constant average factor index k, so if our sieving depth grows merely linearly in p (i.e. we test the same number of k's for every p), our chance of finding a small factor remains roughly constant.

[Fusion_power]

Ewmayer,

So in simple terms, factoring by trial division retains its efficiency no matter how large the exponent because the increasing number of potential factors is countered by the reduced number that are prime and yield 1 or 7 mod 8.

Prime95 uses trial division to test for small factors. It uses p-1 factoring which also tests for small factors. It then uses p-1 with upper and lower bounds to test for small to midsize factors.

This begs a few questions. Why does it not also implement p+1 factoring? Also, could Elliptic Curve be used to any advantage with Mp numbers?

Fusion

[nfortino]

Originally posted by Fusion_power
This begs a few questions. Why does it not also implement p+1 factoring? Also, could Elliptic Curve be used to any advantage with Mp numbers?

Fusion

p+1 factoring (and I believe Elliptic Curve factoring) have a major disadvantage to p-1 factoring. The special form of Mersenne factors means p-1 factoring requires 2kp to be smooth. Because we know 2p will always be a factor of this number, we can edit the standard p-1 factoring method so only k (a much smaller number) needs to be smooth. With p+1 factoring, we have 2kp+2, or 2(kp+1). Since kp+1 is much larger than k, a p+1 test is much less likely to yield a factor than a p-1 test with the same bounds. I can't say I understand Elliptic Curve factoring, but I don't believe it takes advantage of the special form of Mersenne factors either.

As a side note, if anyone could point me to a good book on Elliptic Curve factoring, it would be much appreciated.

[Fusion_power]

Nfortino,

I've studied the p-1 form and p+1 form and they seem to be yin and yang of the same basic group ordering mechanism. Both fail if P + or - 1 yield large primes. The example I am looking at shows (p-1)/4 and (p+1)/6 where p=29 yielding primes of 7 and 5 respectively.

I am looking at a copy of Peter L. Montgomery's A Survey of Modern Integer Factorization Algorithms. Its available as a ghostscript document. I don't have the link currently but it is here on the forum, probably buried several pages back.

ECM appears to be modifiable based on division by 2kp to handle Mp numbers. This is just a superficial look but should be possible.

Fusion

[Fusion_power]

I got a partial answer on the question about sequence to determine which numbers 2kp+1 numbers are viable, i.e. verify if the number is prime first or verify if the number yields 1 or 7 mod 8.

Should always do the 1 or 7 mod 8 test first. Why? Simple, 2kp+1 numbers ALWAYS follow a simple pattern. Here is an example for 2^31-1:

1 1
63 7
125 5
187 3
249 1
311 7
373 5
435 3
497 1
559 7
621 5
683 3
745 1
807 7
869 5
931 3
993 1
1055 7
1117 5
1179 3
1241 1
1303 7
1365 5
1427 3
1489 1
1551 7
1613 5
1675 3
1737 1
1799 7
1861 5
1923 3
1985 1

All you have to do to test for 1 or 7 mod 8 is test the very first number then keep 2 and toss the next 2.

Fusion