Factoring database

[RichD]

After another 80-100 submits on 30 or so numbers (along with previous observations) I find it can easily pull a p22, p23, p24 from larger numbers. But when the composite gets in the low c50s, it has a dickens of a time finding one. I guess it just needs a little more tweaking.

I'm still impressed how many factors can be found in less than two seconds.

P.S. I know it runs a max of four seconds but when the number is fully factored, the results are returned in less than two.

[Syd]

Here is what the button does:

function quick_ecm($number_gecm) {
assert($number_gcem, INT_UNSIGNED);

$fnum = $numbers->get_by_id($number_qecm);
assert($fnum->valid(), true);

$time = new timer();
$time->set(4,0); // 4 seconds
$time->set_action("kill_ecm");

foreach($fnum->get_components() as $f) {
if($f->type != NUMBER_COMPOSITE && $f->type != NUMBER_UNKNOWN) continue;

if($f->digits() < 40) {
  exec("msieve -v \"".$f->get_base(10)."\"",$aus);
  parse_it($f, $aus);
} else {
  $counter = new db_counter($number_qecm);

  $thread = new threads();
  $thread->num = 3;
  if(!$counter->read()) { // P-1, P+1 only on first run
   $thread->addcmd("echo \"".$f->get_base(10)."\" | ecm -pm1 4000", 1); // Start low to avoid finding input number
   $thread->addcmd("echo \"".$f->get_base(10)."\" | ecm -pm1 600000", 1);
   $thread->addcmd("echo \"".$f->get_base(10)."\" | ecm -pp1 200000", 3);
  }
  $thread->addcmd("echo \"".$f->get_base(10)."\" | ecm -c 40 -v -I 3 1000", 3);
  $time->start();
  $thread->start();
  $time->stop();
  
  foreach($thread->get_output() as $out) parse_it($f,$out);
  if($f->type & NUMBER_FACTOR) {
    $counter->delete();
    quick_ecm($number_gecm); // Try again on remaining (composite)?
  } else {
    $counter->inc();
  }

}
}

1. 1 curve P-1 to B1=4k
2. 1 curve P-1 to B1=600k
3. 3 curves P+1 to B1=200k
4. 3 x "ecm -c 40 -v -I 3 1000"

Thats 3x40 curves per run, pulling out a p20 is not that unlikely.

These parameters are just guesses, maybe far from being optimal. Suggestions welcome!

[RichD]

I'm not sure what is going on with the code but several times I had a left-over c12. It took several submits to get the two p6's.

It looks like the msieve would get it the first time??

[jasonp]

Msieve uses trial division and pollard rho first, no 6-digit factors would survive that. Of course if the input is not factored msieve will then happily spend huge amounts of time trying to make further progress...

[RichD]

Originally Posted by jasonp

Msieve uses trial division and pollard rho first, no 6-digit factors would survive that. Of course if the input is not factored msieve will then happily spend huge amounts of time trying to make further progress...

I understand what you are saying. The point I am trying to make is it takes several "submits" to break the c12. Since I don't understand the code Syd provided in post #563, it seems msieve is not called for what appears as < 40 digit input. It appears curves are thrown at it instead. I don't know!

I think the Quick ECM logic has changed again. You may not necessarily get all the factors within 4 seconds. Once it finds a factor (say > 2000?) it stops. You have to submit again on the remaining composite. But, if it can't find a single factor quickly, you do get more time than 4 seconds. In fact, quite a bit more it appears.

[Mini-Geek]

Originally Posted by RichD

I understand what you are saying. The point I am trying to make is it takes several "submits" to break the c12. Since I don't understand the code Syd provided in post #563, it seems msieve is not called for what appears as < 40 digit input. It appears curves are thrown at it instead. I don't know!

I think the Quick ECM logic has changed again. You may not necessarily get all the factors within 4 seconds. Once it finds a factor (say > 2000?) it stops. You have to submit again on the remaining composite. But, if it can't find a single factor quickly, you do get more time than 4 seconds. In fact, quite a bit more it appears.

The code Syd posted means that if the number is under 40 digits, just send it to msieve (for msieve to crack using, apparently, trial division, pollard's rho, SIQS, etc.; whatever it does, it cracks any <c40 near-instantly), otherwise (i.e. the number is over 40 digits) go through the P-1, P+1, and ECM.

[RichD]

Originally Posted by Mini-Geek

The code Syd posted means that if the number is under 40 digits, just send it to msieve (for msieve to crack using, apparently, trial division, pollard's rho, SIQS, etc.; whatever it does, it cracks any <c40 near-instantly), otherwise (i.e. the number is over 40 digits) go through the P-1, P+1, and ECM.

Then why does it (sometimes) take multiple attempts to crack a c12?

P.S. I've also noticed it on c14 & c17, all with the two factors nearly equal.

[RichD]

Originally Posted by RichD

Then why does it (sometimes) take multiple attempts to crack a c12?

P.S. I've also noticed it on c14 & c17, all with the two factors nearly equal.

Go to Home Prime Base 10, seq 8000. There is a c14 left-over. I've run Quick ECM on it 3 times.

Hopefully, to demonstrate my point, it won't crack on your first attempt.

[Mini-Geek]

Originally Posted by RichD

Go to Home Prime Base 10, seq 8000. There is a c14 left-over. I've run Quick ECM on it 3 times.

Hopefully, to demonstrate my point, it won't crack on your first attempt.

huh...it cracked on my first attempt. Sorry.
(since it might be a bit hard to find now, it was 43847865855887)
I tried, locally, each of the factoring methods Syd posted before using the button, and any of the steps except the P+1 (which finds N, because it's overkill) will find the factors near-instantly.
Edit: (which means that there is 0 chance that all was working as it ought to for you) Do you use the DB logged in or not? Maybe that's got something to do with it, for some reason.

a few lines later, Quick ECM found a p25(!) from http://factordb.com/search.php?id=70125489, a c76. The last curve in Quick ECM requires 101 runs to expect a 25-digit factor.
and a few lines after that, I ran the Quick ECM-style curves locally and found a p24.

[RichD]

Originally Posted by Mini-Geek

Edit: (which means that there is 0 chance that all was working as it ought to for you) Do you use the DB logged in or not? Maybe that's got something to do with it, for some reason.

Ah, you might have a point Mini-Geek. I am logged in and the trial I was performing had all the other factors listed above the Quick ECM. In another words, I was going down the line picking primes off but left the c14 for last.

I'm not trying to be a Beavis about this just simply pointing out a few anomalies during my pseudo-testing. Perhaps, as a team effort, we can find optimal values for the Quick ECM as Syd suggested.

I have no idea what they would be but I am just providing a little feedback for discussion.

RichD.

[RichD]

As a follow up, the Quick ECM can easily find a low-to-mid p20 (within 2-3 attempts). The best I have seen was a p33. Larger numbers (c70-c80) can easily pull a p23 out as opposed to/from a c48. In another words, when the factors are about the same size it has a tough time.

This is a marvelous piece of work this FactorDB. I think it just needs a little more time to mature.

Edit: Hint, hint -- I need more points, more queue workers. :-)