Opened 9 years ago

Closed 4 years ago

Last modified 4 years ago

#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) 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)

trac_10951.patch (2.7 KB) - added by zimmerma 9 years ago.

Download all attachments as: .zip

Change History (24)

Changed 9 years ago by zimmerma

comment:1 Changed 9 years ago by zimmerma

  • Cc AlexGhitza cremona added
  • Status changed from new to needs_review

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

comment:2 Changed 9 years ago by zimmerma

  • Cc rlm added

comment:3 follow-up: Changed 9 years ago by mariah

  • 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 9 years ago by zimmerma

  • 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 zimmerma

  • Owner changed from (none) to tbd

comment:6 Changed 8 years ago by was

  • Keywords sd32 added

comment:7 Changed 8 years ago by mhansen

  • Authors set to Paul Zimmerman
  • 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 jdemeyer

  • 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 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:10 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:13 Changed 5 years ago by 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

comment:14 Changed 5 years ago by zimmerma

  • 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 git

  • Commit changed from 5c6c5a249c5ad601998c23f4b3681461a2f13111 to 27c99e1113d17c13c9aa7b9e4917ce7ba7e5404e

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

d6487b0Merge remote-tracking branch 'origin/u/vbraun/fix_python_tarball_names' into 10951
27c99e1fixes and improved documentation

comment:16 Changed 5 years ago by zimmerma

  • Status changed from needs_work to needs_review
  • Work issues documentation deleted

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


New commits:

d6487b0Merge remote-tracking branch 'origin/u/vbraun/fix_python_tarball_names' into 10951
27c99e1fixes and improved documentation

comment:17 Changed 5 years ago by jpflori

  • Cc jpflori added

comment:18 Changed 4 years ago by chapoton

  • 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:

173f5b0patch for #10951 (added optional input of sigma, and return lucky sigma)
45a5de7fixes and improved documentation
4a59ceatrac #10951 not so many random

comment:19 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.9

comment:20 Changed 4 years ago by jpflori

  • 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 4 years ago by vbraun

  • Branch changed from public/ticket/10951 to 4a59cea09beb2c169e73bc3cc55da73843cde4d1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:22 Changed 4 years ago by zimmerma

  • 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

comment:23 Changed 4 years ago by chapoton

  • Authors changed from Paul Zimmerman to Paul Zimmermann
Note: See TracTickets for help on using tickets.