#10951 closed enhancement (fixed)
ecmfactor should take as optional argument the sigma value
Reported by: | zimmerma | Owned by: | tbd |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.9 |
Component: | factorization | Keywords: | sd32, sd40.5 |
Cc: | AlexGhitza, cremona, rlm, jpflori | Merged in: | |
Authors: | Paul Zimmermann | Reviewers: | Mike Hansen, Frédéric Chapoton, Jean-Pierre Flori |
Report Upstream: | N/A | Work issues: | |
Branch: | 4a59cea (Commits, GitHub, GitLab) | Commit: | |
Dependencies: | Stopgaps: |
Description
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.
Attachments (1)
Change History (24)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Cc AlexGhitza cremona added
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
- Cc rlm added
comment:3 follow-up: ↓ 4 Changed 11 years ago by
- Milestone changed from sage-4.7 to sage-4.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 11 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 11 years ago by
- Owner changed from (none) to tbd
comment:6 Changed 11 years ago by
- Keywords sd32 added
comment:7 Changed 10 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 10 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 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:10 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:11 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:12 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:13 Changed 7 years ago by
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
comment:14 Changed 7 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 7 years ago by
- Commit changed from 5c6c5a249c5ad601998c23f4b3681461a2f13111 to 27c99e1113d17c13c9aa7b9e4917ce7ba7e5404e
comment:16 Changed 7 years ago by
- Status changed from needs_work to needs_review
- Work issues documentation deleted
comment:17 Changed 7 years ago by
- Cc jpflori added
comment:18 Changed 7 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 7 years ago by
- Milestone changed from sage-6.4 to sage-6.9
comment:20 Changed 7 years ago by
- Reviewers changed from Mike Hansen to Mike Hansen, Frédéric Chapoton, Jean-Pierre Flori
- Status changed from needs_review to positive_review
comment:21 Changed 7 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 7 years ago by
- Commit 4a59cea09beb2c169e73bc3cc55da73843cde4d1 deleted
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
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