Programming and factoring problem

[ET_]

Originally Posted by axn

If anybody is planning to do ECM on this number, be sure to use Prime95 (v25.11) for stage 1 and gmp-ecm for stage2

Is it only a matter of speed?

Luigi

[axn]

Originally Posted by ET_

Is it only a matter of speed?

Luigi

Yep. Latest Prime95 has _much_ faster FFTs for these forms of numbers. But GMP-ECM has much faster stage 2 implementation.

[lavalamp]

OK, so I figured I'd pour some CPU time into this by looking for the smallest 100, 200, 300 etc. semiprimes.

These semiprimes are of the form 10^(d-1) + k, where d is the number of digits (in base 10).

I can confirm axn's findings for the 100 and 300 digit semiprimes, and I have also found the smallest 700 digit semiprime. Also included is the smallest 400 digit semiprime, and the rest remain unknown.

Here is a table containing a list of candidates for the k values for each corresponding d value. The last item in each list is a known semiprime, but if there are earlier entries in the list it is not known whether it is the smallest for that number of digits.

  d   |       k
 100  |  9
 200  |  49, 103
 300  |  59
 400  |  31
 500  |  21, 51, 187, 217, 247, 267
 600  |  19, 81, 109, 631, 843, 861, 939
 700  |  63
 800  |  79, 167
 900  |  69, 153
1000  |  13, 139

If anyone wants to check my findings I have attached a list of other candidates which I ruled out on the way to finding these. I have only included those with factors over 1 billion.

For the candidate 10^199+49, I have run 1800 ECM curves with B1=1000000. For the rest of the candidates, I have run 700 ECM curves with B1=250000 (except for 10^499+19 and 10^499+81 which I accidentally ran 1400 curves on).

Here are the smallest known semiprimes for each of the values of d:

10^ 99 +   9	= 3079409181853103653   * p81
10^199 + 103	= 4344938347            * p190
10^299 +  59	= 3                     * p299
10^399 +  31	= 615683907928640460029 * p379
10^499 + 267	= 628200761             * p491
10^599 + 939	= 15027771043           * p589
10^699 +  63	= 103493282071          * p688
10^799 + 167	= 3                     * p799
10^899 + 153	= 107                   * p897
10^999 + 139	= 31                    * p998

[10metreh]

Originally Posted by lavalamp

For the candidate 10^199+49, I have run 1800 ECM curves with B1=1000000. For the rest of the candidates, I have run 700 ECM curves with B1=250000 (except for 10^499+19 and 10^499+81 which I accidentally ran 1400 curves on).

What B2? Was this 100*B1 (in which case t30 is 700@25e4 and t35 is 1800@1e6) or the GMP-ECM default (in which case t30 is 430@25e4 and t35 is 904@1e6)?

[smh]

I found one more for 1100

  d    |   k
 1100  |  51

[smh]

  d    |   k
 1200  |  211

[lavalamp]

Originally Posted by 10metreh

What B2? Was this 100*B1 (in which case t30 is 700@25e4 and t35 is 1800@1e6) or the GMP-ECM default (in which case t30 is 430@25e4 and t35 is 904@1e6)?

I left GMP-ECM to decide, it knows far better about these things than I do.

I didn't realised that the GMP-ECM increased B1 means reduced numbers of curves, so I guess I over-curved quite a bit.

Do you have a list for the number of curves to do for various B1 values?

[lavalamp]

OK, I've found quite a lot of lists of curves to run for given B1 values, but I think I'm going to go off this one:
http://www.loria.fr/~zimmerma/records/ecm/params.html

It's right from the horses mouth and appears to be current as it explicitly mentions the latest version of ECM.

[10metreh]

Originally Posted by lavalamp

I didn't realised that the GMP-ECM increased B1

Was this a typo for B2? The B1 is the limit given when you talk about curves you have run, but the B2 also has an effect. This is because a factor will be found if the group order generated by the sigma (which is random) and the factor is B1-smooth, except for the largest factor which must be below B2. This is similar to P-1. Thus the larger the B1 and the larger the B2, the more factors will be found, and this means less curves will be needed to give a good chance that all factors of a certain size have been found.

[lavalamp]

Yes, just a typo, I meant B2 as I specify the B1 values manually (as ECM requires one to).

Incidentally, does anyone know how to reduce the screen outputs of Prime95 while running ECM? They scroll by far too fast to be of any use and I fear they may be draining some performance (every little helps right?).

Each update shows a percentage increase of only about 0.78%. The worker windows only have 5 lines of output visible in them and the quickest worker outputs a line every 0.15 seconds, even the slowest worker outputs every 0.3 seconds.

To be honest, I'd be happy for it not to display any progress at all and just show a start and end line. Maybe with the time that curve took or a timestamp accurate to the second so I can see how things are progressing (currently the timestamps are only accurate to the minute).

I don't know if any of this is possible of course, all of the GUI settings appear to be geared for the mersenne stuff. I just wonder if anyone knows a setting I can add to prime.txt or similar that can alter the screen outputs.

[lavalamp]

I've now done 910 curves at B1=1,000,000 for all of the unfactored candidates with 500, 600, 800 and 900 digits.

Out of the 12 candidates, one was factored:
10^599 + 843 = 110752483387558646661284563486198637 * c564

The remaining candidates are all at the same point now (including the 200 and 1000 digit ones). In otherwords, the next step is 2,351 curves with B1=3,000,000.

I'm running those curves on 10^999 + 13 right now. The eta is a little before 2PM UTC.