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

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.

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

Dsouza,

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

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

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 ?

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

[QUOTE][i]Originally posted by dsouza123 [/i]
[B]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.[/B][/quote]

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

[url]http://www.mersenneforum.org/showthread.php?s=&threadid=1736[/url]

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][b]If a 2kp+1 potential factor is 1 or 7 mod 8 and prime will it always be a true factor?[/B][/QUOTE]

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 [i]smallest[/i] 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.

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

[QUOTE][i]Originally posted by Fusion_power [/i]
[B] 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 [/B][/QUOTE]

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.

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

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

I'll address the last several posts all in one go here:

* p-1 is much more effective than p+1 on M(p) because the special form of factors only requires k to be smooth for p-1 to succeed, whereas k*p+1 must be smooth (much less likely) for p+1 to succeed.

There is an added reason we prefer p-1, which is that p+1 has this quirk of that in roughly half the cases (depending on the initial seed and factor that is found) one is actually effectively doing p-1, and only in the other half is one doing p+1. The problem is, for any given initial seed one doesn't know whether one is doing p+1 or p-1 unless one finds a factor, so in general one needs to run mutliple trials with different initial seeds to make it relatively certain that at least one trial will actually wind up doing p+1.

* ECM works on M(p) without problems, and relies on a similar smoothness property as p+-1 for its success. For ECM, hoever, the smoothness property applies to the unknown (at least until we find a factor) group order of the elliptic curve being tried (which is of the same order of magnitude as the factor itself) rather than any property of the factor itself. George has even coded a special version of ECM in Prime95 which uses the fast Mersenne-mod DWT-based multiply to speed the elliptic curve arithmetic. However, unlike p-1 and p+1, ECM cannot take advantage of any special form of the factors of the number in question. The advantage of ECM over p+-1, of course, is that one can try virtually as many curves as one likes, and only needs to find one with a suitably smooth group order. So you can think of p-1 as being something like a single very cheap (i.e. one can afford to run to very deep bounds) ECM curve, with a guaranteed-better-than-average (because a number the size of k is more likely to be smooth than one the size of 2*k*p) chance of sucess.

* Re. the q == +-1 mod 8 requirement: this is easily handled via a bitwise sieve. If the number of bits in the sieve is a multiple of the computer's natural wordlength (typically 32 or 64) and each sieve bit corresponds to a single value of k, then one just zeroes the bits corresponding to the q != +-1 mod 8 cases in the first word of the sieve array, and copies the result to the remaining words. Then one typically proceeds to kncock out bits corresponding to q's that are multiples of small primes, which are also periodic, but with frequency set by the small prime in question.

And while we're on the subject of factoring, this just in from one of my remote-terminal screens (from some code I'm working on):

M(618970019642690137449562201) has a factor: 302234395011250596454696928877487 .

That mersenne is enormous.

Did you write the code ?

What language is the code in ?

Is it trial factoring, P-1 factoring, something else ?

How long did it take for the program find the factor ?

What type of machine is the program running on ?

Is that the largest mersenne that you have found a factor for ?

Ah, it's nowhere near as big as some of the Fermat numbers the Proth.exe users have been finding factors for, but I take comfort in the fact that I can sieve to a slightly deeper value of k. ;)

As to your other questions:

I wrote the code.

C, with a few ASM macros for key operations (e.g. 128-bit-wide integer multiply and related operations).

Sieve-based TF.

Under a second (k is only 244143, so in that sense the factor is not large).

Some Alphas and Itaniums.

Yes, but I expect to find quite a few more, as part of a QA effort that is sieving a bunch of consecutive primes of around 90 bits (I have a pretty good estimate of how many of these should yield factors below my sieving bound, so if there's a big discrepancy between that and the number I actually find, there's a good chance that more debugging is needed.)

In response to nfortino's question about a good source on elliptic curve factoring, I would recommend the book by Silverman and Tate as a good introduction to elliptic curves in general, and it contains a section on factoring. Crandall and Pomerance also has a good introduction to this method. I gave a non-technical description of the main ideas of ECM in the following thread:
[URL=http://www.mersenneforum.org/showthread.php?s=&threadid=194]Elliptic Curve Method - the theory[/URL]

Here are some more factors found by the 128-bit routines I'm testing. I sieved up to 2^127,
as it's 10-20% more expensive to test a factor candidate between 2^127 and 2^128 than one
less than 2^127.

My first set of runs was for a bunch of consecutive primes >= 2^89 - 1. In the code below,
"q > 2^127" means that the number in question has no factors < 2^127. In cases where a factor
was found, k is the factor index (i.e. the k in q = 2*p*k + 1) and the pass number indicates
during which of the 16 passes (corresponding to the 16 values of k mod 60 for which the q's
are not divisible by 3 or 5 and == +-1 modulo 8, satisfying the quadratic residue condition)
the factor was found. Each of these factoring runs needed roughly 8 hours of CPU time on a
1GHz-class Alpha or Itanium processor.

[code]
M(2^89 - 1) q > 2^127
M(2^89 + 29) q > 2^127
M(2^89 + 89) has a factor: 302234395011250596454696928877487 (pass 0, k = 244143)
M(2^89 + 107) q > 2^127
M(2^89 + 317) q > 2^127
M(2^89 + 447) q > 2^127
M(2^89 + 509) q > 2^127
M(2^89 + 515) q > 2^127
M(2^89 + 531) q > 2^127
M(2^89 + 569) q > 2^127
M(2^89 + 659) q > 2^127
M(2^89 + 705) has a factor: 129254126647357748845154603600147247439 (pass 7, k = 104410652007)
M(2^89 + 741) has a factor: 16281387396681321375473301285313 (pass 2, k = 13152)
has a factor: 4065419847813974530374226801018121 (pass 9, k = 3284020)
M(2^89 + 767) has a factor: 8500895873631488500943774707287503 (pass 7, k = 6866969)
M(2^89 + 789) q > 2^127
M(2^89 + 837) has a factor: 66648179934785163963991168021872959 (pass 8, k = 53837971)
has a factor: 27749727055563087796532825984988799 (pass 12, k = 22416051)
M(2^89 + 861) q > 2^127
M(2^89 + 1059) has a factor: 1237940039285380274899126343 (pass 0, k = 1)
M(2^89 + 1107) q > 2^127
M(2^89 + 1275) has a factor: 90369622867832760067636254503 (pass 3, k = 73)
M(2^89 + 1337) has a factor: 301304702041747275868248293958017 (pass 6, k = 243392)
has a factor: 27333716067421196469772721907841 (pass 15, k = 22080)
M(2^89 + 1521) has a factor: 356832992728148565109437597097099337 (pass 4, k = 288247396)
M(2^89 + 1547) has a factor: 39614081257132168796772074177 (pass 8, k = 32)
M(2^89 + 1637) q > 2^127
M(2^89 + 1829) q > 2^127
M(2^89 + 1845) q > 2^127
M(2^89 + 1847) q > 2^127
M(2^89 + 1877) q > 2^127
M(2^89 + 1917) has a factor: 20749009011498958815641193853381129 (pass 9, k = 16760916)
has a factor: 419661673317743913190804411663 (pass 10, k = 339)
M(2^89 + 2079) q > 2^127
M(2^89 + 2081) q > 2^127
M(2^89 + 2097) has a factor: 642484690688915935771273153299911 (pass 14, k = 518995)
M(2^89 + 2135) q > 2^127
M(2^89 + 2255) q > 2^127
M(2^89 + 2417) q > 2^127
M(2^89 + 2585) has a factor: 683049509896219276619168331821623 (pass 0, k = 551763)
M(2^89 + 2615) q > 2^127
M(2^89 + 2661) has a factor: 38376141217846788521873015927 (pass 7, k = 31)
M(2^89 + 2675) has a factor: 14855280471424563298789554889 (pass 3, k = 12)
M(2^89 + 2679) q > 2^127
M(2^89 + 2729) has a factor: 775820736440265674420109269098447 (pass 0, k = 626703)
has a factor: 89962340594907869957194653120623 (pass 2, k = 72671)
M(2^89 + 2795) q > 2^127
M(2^89 + 2847) q > 2^127
M(2^89 + 2907) has a factor: 417185793239173152641006822807 (pass 9, k = 337)
M(2^89 + 2961) q > 2^127
M(2^89 + 3045) has a factor: 24011198892462850066928822290332889 (pass 3, k = 19396092)
has a factor: 1832151258142362806850712864721 (pass 10, k = 1480)
M(2^89 + 3155) has a factor: 479835462747327677593102188022673 (pass 1, k = 387608)
M(2^89 + 3159) has a factor: 7636852102351510915852736313599 (pass 14, k = 6169)
M(2^89 + 3221) q > 2^127
M(2^89 + 3225) q > 2^127
M(2^89 + 3285) q > 2^127
M(2^89 + 3389) q > 2^127
M(2^89 + 3417) q > 2^127
M(2^89 + 3495) q > 2^127
M(2^89 + 3507) has a factor: 4619992226613039185923557780217 (pass 3, k = 3732)
M(2^89 + 3539) q > 2^127
M(2^89 + 3575) q > 2^127
M(2^89 + 3627) q > 2^127
M(2^89 + 3659) q > 2^127
M(2^89 + 3717) q > 2^127
M(2^89 + 3869) q > 2^127
M(2^89 + 3911) q > 2^127
M(2^89 + 3915) q > 2^127
M(2^89 + 3981) q > 2^127
M(2^89 + 4019) q > 2^127
M(2^89 + 4071) q > 2^127
M(2^89 + 4155) has a factor: 1145264551310152090552511416114821959 (pass 8, k = 925137337)
M(2^89 + 4205) q > 2^127
M(2^89 + 4275) q > 2^127
M(2^89 + 4377) q > 2^127
M(2^89 + 4395) q > 2^127
M(2^89 + 4409) q > 2^127
M(2^89 + 4451) has a factor: 144838984596389492163198575743 (pass 14, k = 117)
M(2^89 + 4485) has a factor: 8011947934254981139147190031569 (pass 13, k = 6472)
M(2^89 + 4491) q > 2^127
M(2^89 + 4619) q > 2^127
M(2^89 + 4649) q > 2^127
M(2^89 + 4689) q > 2^127
M(2^89 + 4745) has a factor: 1525142128399588498675732735649 (pass 8, k = 1232)
has a factor: 1322119961956786133592274806553 (pass 13, k = 1068)
M(2^89 + 4785) q > 2^127
M(2^89 + 4881) q > 2^127
M(2^89 + 4887) q > 2^127
M(2^89 + 4937) q > 2^127
M(2^89 + 4991) q > 2^127
M(2^89 + 5067) q > 2^127
M(2^89 + 5079) q > 2^127
M(2^89 + 5097) q > 2^127
M(2^89 + 5121) has a factor: 2652905504188569929108845160639 (pass 10, k = 2143)
M(2^89 + 5145) q > 2^127
M(2^89 + 5247) has a factor: 1237940039285380274899134719 (pass 0, k = 1)
M(2^89 + 5411) has a factor: 10040976224485133683396780726967657 (pass 13, k = 8111036)
M(2^89 + 5465) q > 2^127
M(2^89 + 5475) q > 2^127
M(2^89 + 5499) has a factor: 32090541520396566593621904463757327 (pass 3, k = 25922533)
M(2^89 + 5531) q > 2^127
M(2^89 + 5577) q > 2^127
M(2^89 + 5699) q > 2^127
M(2^89 + 5735) has a factor: 194866617463990279832422747863929 (pass 8, k = 157412)
M(2^89 + 5751) q > 2^127
M(2^89 + 5837) has a factor: 134978792183481438273627282638431 (pass 2, k = 109035)
M(2^89 + 5849) q > 2^127
M(2^89 + 5867) q > 2^127
[/code]

MOD 8 ?
 

Here is a little answer to answer Fusion_power's last post ( "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: " )


Look at your pattern for 2^3-1 and 2^5-1 :

2^3-1
value -- MOD 8

1 1
7 7
13 5
19 3
25 1
31 7
37 5


2^5-1
value -- MOD 8
1 1
11 3
21 5
31 7
41 1
51 3
61 5
71 7


There is ALWAYS a pattern, but not always the same pattern. Actually, the 1 and the 5 will always be at the same location in this pattern, but not the 3 and 7.


There is also a VERY EASY way of finding MOD 8 : Just look at the last 3 bits of the number. For those who don't program, a computer stores values in binary. Numbers
look like this :

decimal binary
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
11 1011
12 1100
...

Notice that if you look at only the last 3 digits in binary, you know the MOD 8 ? The computer does this in one simple instruction.

So yes, it is MUCH easier to verify MOD 8 then to look if a number is prime.

Re: MOD 8 ?
 

[QUOTE][i]Originally posted by JoCo [/i]
[B]Notice that if you look at only the last 3 digits in binary, you know the MOD 8 ? The computer does this in one simple instruction.[/B][/QUOTE]

Not necessarily. If you're working in a high-level language like C, doing a mod via a%b invokes the math library mod utility, which is generally very slow - it may take literally hundreds of cycles. Luckily, if the modulus is a power of 2, say 2^k, we can define x = 2^k - 1 and replace the expensive library mod with ... & x. The bitwise AND only needs one cycle, as you say.

What to do for general (i.e. non-power-of-2) moduli? That depends on what type of operation it is whose result needs to be modded. If it's a multiply, and we're doing lots of these modulo the same (odd) number, we can use the Montgomery-style modmul, which requires several quantities to be precomputed but is very fast once that is done, assuming integer multiply is fast. If MUL is slow, it may be better to effect the mod via a sequence of bitwise shifts and subtracts, i.e. to get A % B, we left-shift B until its leading ones bit is in the same position as that of A, then repeatedly perform

[code]
if(A >= B)
A -= B;
B >>= 1;
[/code]

until B is back to its original unshifted value.

Another common operation is where we repeatedly increment some integer A by B, modulo C. In that case we precalculate B%C, and add [b]that[/b] to A. Of course the add may still yield a result that needs modding, but we can do that via a simple conditional subtract. One can even avoid the conditional branch here by always sbtracting C, and re-adding it if the result is less than zero (this example assumes all variables are 32-bit unsigned twos-complement ints:

[code]
A = A%C;
BmodC = B%C;

while(whatever)
{
A += BmodC - C; // Subtract off C...
A += (-(A >> 31)) & C; // ...and restore it if result was < 0.
}
[/code]