#10951 closed enhancement (fixed)
ecmfactor should take as optional argument the sigma value
Reported by:  zimmerma  Owned by:  tbd 

Priority:  minor  Milestone:  sage6.9 
Component:  factorization  Keywords:  sd32, sd40.5 
Cc:  AlexGhitza, cremona, rlm, jpflori  Merged in:  
Authors:  Paul Zimmermann  Reviewers:  Mike Hansen, Frédéric Chapoton, JeanPierre Flori 
Report Upstream:  N/A  Work issues:  
Branch:  4a59cea (Commits)  Commit:  
Dependencies:  Stopgaps: 
Description
I suggest the ecmfactor
function takes as optional argument a sigma
value, which would be passed to GMPECM. 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 61digit 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 GMPECM if not sigma was given, but that might be more difficult to implement.
Attachments (1)
Change History (24)
Changed 9 years ago by
comment:1 Changed 9 years ago by
 Cc AlexGhitza cremona added
 Status changed from new to needs_review
comment:2 Changed 9 years ago by
 Cc rlm added
comment:3 followup: ↓ 4 Changed 9 years ago by
 Milestone changed from sage4.7 to sage4.7.1
 Status changed from needs_review to needs_work
This function seems to lack documentation. I do not see anything about it at http://sagemath.org/doc/reference/libs.html.
comment:4 in reply to: ↑ 3 Changed 9 years ago by
 Owner changed from tbd to (none)
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
comment:5 Changed 9 years ago by
 Owner changed from (none) to tbd
comment:6 Changed 9 years ago by
 Keywords sd32 added
comment:7 Changed 8 years ago by
 Keywords sd40.5 added
 Reviewers set to Mike Hansen
 Status changed from needs_work to positive_review
Looks good to me. I've made #13042 to add the module to the reference manual.
comment:8 Changed 8 years ago by
 Status changed from positive_review to needs_work
 Work issues set to rebase, documentation
This patch should still be rebased to #12777 and the new option should be documented.
comment:9 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:10 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:11 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:12 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:13 Changed 5 years ago by
any progress on this? I just found a 59digit 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
comment:14 Changed 5 years ago by
 Branch set to u/zimmerma/10951
 Commit set to 5c6c5a249c5ad601998c23f4b3681461a2f13111
 Work issues changed from rebase, documentation to documentation
rebased with the help of Marc Mezzarobba. Remains to do:
 check tests
 add documentation
comment:15 Changed 5 years ago by
 Commit changed from 5c6c5a249c5ad601998c23f4b3681461a2f13111 to 27c99e1113d17c13c9aa7b9e4917ce7ba7e5404e
comment:16 Changed 5 years ago by
 Status changed from needs_work to needs_review
 Work issues documentation deleted
comment:17 Changed 5 years ago by
 Cc jpflori added
comment:18 Changed 5 years ago by
 Branch changed from u/zimmerma/10951 to public/ticket/10951
 Commit changed from 27c99e1113d17c13c9aa7b9e4917ce7ba7e5404e to 4a59cea09beb2c169e73bc3cc55da73843cde4d1
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

comment:19 Changed 5 years ago by
 Milestone changed from sage6.4 to sage6.9
comment:20 Changed 5 years ago by
 Reviewers changed from Mike Hansen to Mike Hansen, Frédéric Chapoton, JeanPierre Flori
 Status changed from needs_review to positive_review
comment:21 Changed 5 years ago by
 Branch changed from public/ticket/10951 to 4a59cea09beb2c169e73bc3cc55da73843cde4d1
 Resolution set to fixed
 Status changed from positive_review to closed
comment:22 Changed 5 years ago by
 Commit 4a59cea09beb2c169e73bc3cc55da73843cde4d1 deleted
thank you Frederic for your review. For ecmfactor(2^1671, 2e5)
the 7digit factor is always found by ECM since the curve has order divisible by 12 at least. However the 44digit factor might be found in some (very) rare cases, which was the reason for the "random" keyword. The other cases are fine.
Paul
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 nontrivial factor was found (with a random or usergiven sigma) it is returned by ecmfactor, which now returns (True, N, sigma)
Paul