 mersenneforum.org > Math Interesting observation re 2kp+1 numbers
 Register FAQ Search Today's Posts Mark Forums Read  2003-12-29, 17:34 #1 Fusion_power   Aug 2003 Snicker, AL 23×3×52 Posts Interesting observation re 2kp+1 numbers 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 Last fiddled with by Fusion_power on 2003-12-29 at 17:42   2003-12-29, 19:44 #2 dsouza123   Sep 2002 2·331 Posts 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.   2003-12-29, 20:14 #3 michael   Dec 2003 Belgium 5×13 Posts 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' 2003-12-30, 01:40 #4 Fusion_power   Aug 2003 Snicker, AL 23×3×52 Posts 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   2003-12-30, 03:41 #5 dsouza123   Sep 2002 2×331 Posts 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 ?   2003-12-30, 15:35 #6 Fusion_power   Aug 2003 Snicker, AL 23·3·52 Posts 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   2003-12-30, 15:46   #7
ewmayer
2ω=0

Sep 2002
República de California

100110011010102 Posts Quote:
 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

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.

Quote:
 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.

Last fiddled with by ewmayer on 2003-12-30 at 15:47   2003-12-30, 17:00 #8 Fusion_power   Aug 2003 Snicker, AL 23×3×52 Posts 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   2003-12-30, 17:25   #9
nfortino

Nov 2003

3×5×11 Posts Quote:
 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.   2003-12-30, 18:37 #10 Fusion_power   Aug 2003 Snicker, AL 23×3×52 Posts 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   2003-12-30, 19:20 #11 Fusion_power   Aug 2003 Snicker, AL 11308 Posts 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   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post xilman Lounge 1 2016-08-07 20:32 jnml Miscellaneous Math 9 2014-04-28 20:43 petrw1 Math 5 2008-11-04 20:27 MooooMoo Lounge 15 2006-11-14 03:40 Xyzzy Hardware 0 2003-08-21 21:29

All times are UTC. The time now is 17:22.

Sun Nov 29 17:22:01 UTC 2020 up 80 days, 14:32, 4 users, load averages: 1.35, 1.52, 1.45