ecmfactor should take as optional argument the sigma value

[zimmerma]

I suggest the ecmfactor function takes as optional argument a sigma value, which would be passed to GMP-ECM. In case of a successful factorization, this would allow to know the lucky curve, for example to report it on some tables of records.

For example I found a 61-digit prime factor using ecmfactor, but was unable to know the lucky sigma (​http://www.loria.fr/~zimmerma/records/ecmnet.html).

Alternatively, one could store the (random) sigma value chosen by GMP-ECM if not sigma was given, but that might be more difficult to implement.

[zimmerma]

the attached file does two things:

(1) if an optional sigma=nnn input is given to ecmfactor, it uses that value (nnn) to choose the elliptic curve, instead of a random one. This allows to get a deterministic behaviour;

(2) if a non-trivial factor was found (with a random or user-given sigma) it is returned by ecmfactor, which now returns (True, N, sigma)

Paul

[mariah]

This function seems to lack documentation. I do not see anything about it at ​http://sagemath.org/doc/reference/libs.html.

[zimmerma]

Replying to mariah:

This function seems to lack documentation. I do not see anything about it at ​http://sagemath.org/doc/reference/libs.html.

you are right. However this was already the case before my patch. The best would be to open a separate ticket to add documentation for this function.

Paul

[mhansen]

Looks good to me. I've made #13042 to add the module to the reference manual.

[jdemeyer]

This patch should still be rebased to #12777 and the new option should be documented.

[zimmerma]

any progress on this? I just found a 59-digit factor with ecmfactor, but I'm unable to know which sigma value was used. If I was able to give the sigma value, I would know.

Paul

[zimmerma]

rebased with the help of Marc Mezzarobba. Remains to do:

• check tests
• add documentation

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d6487b0	Merge remote-tracking branch 'origin/u/vbraun/fix_python_tarball_names' into 10951
​27c99e1	fixes and improved documentation

[zimmerma]

I've added documentation in the new patch 27c99e1. Ready for review again. Paul

---

New commits:

​d6487b0	Merge remote-tracking branch 'origin/u/vbraun/fix_python_tarball_names' into 10951
​27c99e1	fixes and improved documentation

[chapoton]

this looks good to me.

I have removed some of the newly introduced random keywords.

If somebody else agrees, this can be put into positive review.

---

New commits:

​173f5b0	patch for #10951 (added optional input of sigma, and return lucky sigma)
​45a5de7	fixes and improved documentation
​4a59cea	trac #10951 not so many random

[zimmerma]

thank you Frederic for your review. For ecmfactor(2^167-1, 2e5) the 7-digit factor is always found by ECM since the curve has order divisible by 12 at least. However the 44-digit factor might be found in some (very) rare cases, which was the reason for the "random" keyword. The other cases are fine.

Paul