pretest option minimum size

[James Heinrich]

When I run through a set of numbers I want to factor I usually start with the -pretest option (to sift out the easy factorizations, I can continue the hard ones later), but sometimes yafu finds a small composite during ECM that could easily be factored in a few seconds but the pretest option prevents siqs from running. What I'd like to see is some option like "-pretest_threshold <digits>" where siqs is allowed to run on composites less than <digits> digits.

[bsquared]

Originally Posted by James Heinrich

When I run through a set of numbers I want to factor I usually start with the -pretest option (to sift out the easy factorizations, I can continue the hard ones later), but sometimes yafu finds a small composite during ECM that could easily be factored in a few seconds but the pretest option prevents siqs from running. What I'd like to see is some option like "-pretest_threshold <digits>" where siqs is allowed to run on composites less than <digits> digits.

Do those small composites get added to the list of numbers to factor later, or are they ignored and lost? Just want to clarify if this is a problem (as some numbers would be lost from a complete factorization), or an optimization/preference (just a desire to get these small ones done first).

[James Heinrich]

No, nothing is lost, I just want to get the small ones done first.

As a random example (edited for brevity):

Starting factorization of 14156161707358647804728644991232561131993674306133067594227858606703236064990613537256494257288902246641757583573171692305069299841687536
div: found prime factor = 2
div: found prime factor = 2
div: found prime factor = 2
div: found prime factor = 2
div: found prime factor = 3
div: found prime factor = 271
div: found prime factor = 1831
scheduled 30 curves at B1=2000 toward target pretesting depth of 43.00
prp13 = 2893511660873 (curve 4 stg2 B1=2000 sigma=303770396 thread=0)
Finished 4 curves using Lenstra ECM method on C129 input, B1=2K, B2=gmp-ecm default
Finished 26 curves using Lenstra ECM method on C117 input, B1=2K, B2=gmp-ecm default
Finished 74 curves using Lenstra ECM method on C117 input, B1=11K, B2=gmp-ecm default
Finished 216 curves using Lenstra ECM method on C117 input, B1=50K, B2=gmp-ecm default
pm1: starting B1 = 3750K, B2 = gmp-ecm default on C117
prp29 = 32895160657610218397548809017 (curve 40 stg2 B1=250000 sigma=303537196 thread=0)
Finished 240 curves using Lenstra ECM method on C117 input, B1=250K, B2=gmp-ecm default
prp28 = 3347338785154139067312669731 (curve 30 stg2 B1=250000 sigma=1688092289 thread=2)
Finished 180 curves using Lenstra ECM method on C88 input, B1=250K, B2=gmp-ecm default
final ECM pretested depth: 30.44
c61 cofactor = 1865476249140792141927330175598826930439956399426237147045167
Total factoring time = 90.5932 seconds

We end up with a c61 at the end which would take not even a second to to split into p30+p32, but with the pretest option enabled siqs can't run. I would like it to be allowed to run for "small" numbers (according to the parameter I specify) but not run for larger numbers (e.g. I'll come back and deal with those later, or on a different machine).

[James Heinrich]

Just following up on this request -- is this likely to be included in an upcoming version?

Just in case my idea isn't clear, (my understanding of) the current logic is something crudely like:

while (ECM_LEVEL_T_LEVEL < UNFACTORED_DIGITS * ECM_RATIO) {
  doECMandPM1();
}
if (COFACTOR_IS_COMPOSITE) {
  if (OPTION_PRETEST) {
    // give up, output composite cofactor
  } else {
    doSIQSorNFS(COFACTOR);
  }
}

My suggestion is to change that last part to:

if (OPTION_PRETEST && (OPTION_PRETEST < UNFACTORED_DIGITS)) {
  // give up, output composite cofactor
} else {
  doSIQSorNFS(COFACTOR);
}

Such that when I specify -pretest it always gives up before SIQS (current behaviour), but if I specify -pretest 90 it will only output composites if they're larger than c90, smaller ones will be completely factored.

Does that make sense?