ecmfactor should take as optional argument the sigma value

[zimmermann6]

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.

CC: @aghitza @JohnCremona @rlmill @jpflori

Component: factorization

Keywords: sd32, sd40.5

Author: Paul Zimmermann

Branch: 4a59cea

Reviewer: Mike Hansen, Frédéric Chapoton, Jean-Pierre Flori

Issue created by migration from https://trac.sagemath.org/ticket/10951

[zimmermann6]

comment:1

Attachment: trac_10951.patch.gz

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

[sagetrac-mariah]

comment:3

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

[zimmermann6]

comment:4

Replying to @sagetrac-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

[williamstein]

Changed keywords from none to sd32

[mwhansen]

Author: Paul Zimmerman

[mwhansen]

Reviewer: Mike Hansen

[mwhansen]

comment:7

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

[mwhansen]

Changed keywords from sd32 to sd32, sd40.5

[jdemeyer]

Work Issues: rebase, documentation

[jdemeyer]

comment:8

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

[zimmermann6]

comment:13

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

[zimmermann6]

comment:14

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

• check tests
• add documentation

[zimmermann6]

Changed work issues from rebase, documentation to documentation

[zimmermann6]

Branch: u/zimmerma/10951

[zimmermann6]

Commit: 5c6c5a2

[sagetrac-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

[sagetrac-git]

Changed commit from 5c6c5a2 to 27c99e1

[zimmermann6]

comment:16

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

[zimmermann6]

Changed work issues from documentation to none

[fchapoton]

comment:18

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

[fchapoton]

Changed branch from u/zimmerma/10951 to public/ticket/10951

[fchapoton]

Changed commit from 27c99e1 to 4a59cea

[jpflori]

Changed reviewer from Mike Hansen to Mike Hansen, Frédéric Chapoton, Jean-Pierre Flori

[vbraun]

Changed branch from public/ticket/10951 to 4a59cea

[zimmermann6]

Changed commit from 4a59cea to none

[zimmermann6]

comment:22

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

[fchapoton]

Changed author from Paul Zimmerman to Paul Zimmermann