who can factor 10^100+27?

[FactorEyes]

Originally Posted by bsquared

Is the heuristic broken for jobs this tiny, or is msieve not handleing it right somehow?

I recently had problems in post-processing with a 128-digit snfs job. I've been meaning to send Jason the logs. Sounds as if that is a good idea.

[jasonp]

Probably 2^25 isn't "asymptotic" enough for the heuristic to be accurate, but that's no excuse for the filtering to not work. It's surprising how difficult it is to make the filtering work in the presence of a huge amount of excess; so much effort goes into preserving the available excess that the code has a difficult time "letting go", especially for small problems.

The basic problem is that when there are loads of relations, there are loads of large primes and this makes the automatically chosen filtering bounds too large to be useful. The code attempts to correct its initial guess but the process appears to need more work (see my talk on the CADO workshop site for much more detail)

[bsquared]

Originally Posted by jasonp

Probably 2^25 isn't "asymptotic" enough for the heuristic to be accurate, but that's no excuse for the filtering to not work. It's surprising how difficult it is to make the filtering work in the presence of a huge amount of excess; so much effort goes into preserving the available excess that the code has a difficult time "letting go", especially for small problems.

The basic problem is that when there are loads of relations, there are loads of large primes and this makes the automatically chosen filtering bounds too large to be useful. The code attempts to correct its initial guess but the process appears to need more work (see my talk on the CADO workshop site for much more detail)

Cool, thanks for the info.

By the way, I hope it didn't come across that I was bashing on you for this not *just working*. I know that I'm spoiled by exactly that being the case the vast majority of the time. I appreciate that there is a hard balance to achieve, and if anything, I would rather have difficulty for very small jobs like this when it's easy to guess wrong and end up with 3x the amount of relations than I really need, then have difficulty for large jobs. It's harder to end up with 3x the needed relations when one is gathering 200 million of them.

The workaround is trivial:
head -n 1200000 data.dat > msieve.dat

[jasonp]

No bashing was inferred. In fact if the code could be made to work with an arbitrary amount of excess then perhaps larger jobs could be massively oversieved in order for the postprocessing to fit in smaller machines.

[10metreh]

aaa120, you're worse than me! Everyone knows PARI shouldn't be used for factoring!

[xilman]

Originally Posted by 10metreh

aaa120, you're worse than me! Everyone knows PARI shouldn't be used for factoring!

On the contrary, I use PARI for factoring quite often.

When extending tables, for instance, ECM, P+1 and P-1 quite often find composite factors of 25-50 digits. My usual way of splitting them is to extract them from the output of the previously run program and feed them into PARI. A quick cut and paste later and I've a list of prime factors to feed into subsequent scripts.

I think you meant to say something like "PARI shouldn't be used to find large factors".


Paul

[10metreh]

Originally Posted by xilman

I think you meant to say something like "PARI shouldn't be used to find large factors".

Correct. PARI only uses MPQS, not SIQS.