Interesting observation re 2kp+1 numbers

[ewmayer]

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.

[ewmayer]

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 .

[dsouza123]

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 ?

[ewmayer]

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.)

[philmoore]

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:
Elliptic Curve Method - the theory

[ewmayer]

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.

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

[JoCo]

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.

[ewmayer]

Originally posted by JoCo
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.

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

if(A >= B)
    A -= B;
B >>= 1;

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 that 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:

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.
}