Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#7239 closed enhancement (fixed)

factorization of Cunningham numbers

Reported by: ylchapuy Owned by: tbd
Priority: major Milestone: sage-4.3.1
Component: factorization Keywords: integer factorization Cunningham
Cc: Minh Van Nguyen Merged in: sage-4.3.1.alpha2
Authors: Yann Laigle-Chapuy Reviewers: John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by ylchapuy)

A small spkg to provide factorization of Cunningham numbers.

The raw data is from http://cage.ugent.be/~jdemeyer/cunningham

Some applications are in ticket #7240

Attachments (1)

trac7239_Cunningham_factorization.patch (3.9 KB) - added by ylchapuy 13 years ago.
based on 4.1.2

Download all attachments as: .zip

Change History (20)

comment:2 Changed 13 years ago by ylchapuy

Description: modified (diff)
Summary: factorization of Cunningham numbersfactorization of Cunningham numbers [with patch and spkg, needs review]

Changed 13 years ago by ylchapuy

based on 4.1.2

comment:3 Changed 13 years ago by ylchapuy

Summary: factorization of Cunningham numbers [with patch and spkg, needs review][with patch and spkg, needs review] factorization of Cunningham numbers

comment:4 Changed 13 years ago by ylchapuy

Cc: Minh Van Nguyen added

mvngu, I add cc'ed you as you were interested in ticket #191

comment:5 Changed 13 years ago by ylchapuy

Status: newneeds_review

comment:6 Changed 13 years ago by John Cremona

Report Upstream: N/A
Status: needs_reviewneeds_work

I tried to install using "sage -i cunningham_tables-1.0.spkg" after downloading it, but I had error messages:

...
Finished extraction
sage: After decompressing the directory cunningham_tables-1.0 does not exist
This means that the corresponding .spkg needs to be downloaded
...

Should I have applied the patch first? It would help to give more detailed instructions!

Separate question: did you ask Jeroen Demeyer about using his data?

comment:7 Changed 13 years ago by ylchapuy

Status: needs_workneeds_review
Summary: [with patch and spkg, needs review] factorization of Cunningham numbersfactorization of Cunningham numbers

Concerning the package, the failure was of course due to a silly mistake I made. The new spkg should work.

the procedure you tried was the good one:

  • download the spkg
  • install it with sage -i cunningham_tables-1.0.spkg
  • apply the patch

Concerning the author of the data I used, I just wrote him an email to ask for an "official"comment on this use of the data he collected and will send his answer as soon as I get it.

comment:8 Changed 13 years ago by John Cremona

Where is the "new" spkg? Is it still called cunningham_tables-1.0.spkg? I downloaded it (again, assuming it had changed) but the same thing happened.

I expect Jeroen will be amenable (if necessary I could also ask him as I know him).

comment:9 Changed 13 years ago by ylchapuy

the new spkg is at the same address. I tested it again and it works for me now.

The previous one was creating a directory named "cunningham_tables" when decompressed, then only difference with the new one is that the directory is now named "cunningham_tables-1.0". You might check you have the right one by trying for yourself:

tar tjf cunningham_tables-1.0.spkg should answer

cunningham_tables-1.0/
cunningham_tables-1.0/.hg/
cunningham_tables-1.0/.hg/store/
cunningham_tables-1.0/.hg/store/fncache
cunningham_tables-1.0/.hg/store/undo
cunningham_tables-1.0/.hg/store/00manifest.i
cunningham_tables-1.0/.hg/store/00changelog.i
cunningham_tables-1.0/.hg/store/data/
cunningham_tables-1.0/.hg/store/data/_s_p_k_g.txt.i
cunningham_tables-1.0/.hg/store/data/read__cunningham__prime__factors.py.i
cunningham_tables-1.0/.hg/store/data/spkg-install.i
cunningham_tables-1.0/.hg/requires
cunningham_tables-1.0/.hg/dirstate
cunningham_tables-1.0/.hg/undo.dirstate
cunningham_tables-1.0/.hg/00changelog.i
cunningham_tables-1.0/.hg/branch
cunningham_tables-1.0/.hg/undo.branch
cunningham_tables-1.0/src/
cunningham_tables-1.0/src/cunningham_tables/
cunningham_tables-1.0/src/cunningham_tables/cunningham_prime_factors.sobj
cunningham_tables-1.0/spkg-install
cunningham_tables-1.0/SPKG.txt
cunningham_tables-1.0/read_cunningham_prime_factors.py

comment:10 Changed 13 years ago by ylchapuy

from Jeroen Demeyer:

"You are certainly welcome to use this data (I don't think pure data like this can be copyrighted anyway). I actually know about Sage (even though I use PARI/GP myself) and certainly would like to support the project. It is not entirely clear what your function should do: it is supposed to be incorporated into the general factor() function or do you plan to add a special function somehow? I'm just asking so that I can help you better.

You might also want to have at my fullfactor() PARI/GP package (see http://cage.ugent.be/~jdemeyer/parigp/fullfactor.html). This is a package I wrote with some helper functions for factoring (some unrelated to the Cunningham tables). It contains a function factor_cyclo(n) which basically tries to find factors of cyclotomic polynomials in a given number. It then looks these factors up in the Cunningham tables. It also contains some more low-level functions to help with the factorization of numbers of the form b^e-1 (or divisors of these). The code works but I admit it is not very good-looking. Note however that this code has been written for PARI/GP 2.4 while Sage still uses PARI/GP 2.3 I believe.

Best regards, Jeroen."

comment:11 in reply to:  9 Changed 13 years ago by John Cremona

Replying to ylchapuy:

the new spkg is at the same address. I tested it again and it works for me now.

The previous one was creating a directory named "cunningham_tables" when decompressed, then only difference with the new one is that the directory is now named "cunningham_tables-1.0". You might check you have the right one by trying for yourself:

OK, what was apparently happening is that when I downloaded the new file, firefox was only getting the cached version -- I had to manually clear the cache! now I get the correct new version and it installs fine. I will continue to review this by applying the patch, etc, soon but cannot right now.

comment:12 Changed 13 years ago by John Cremona

Keywords: integer factorization Cunningham added
Reviewers: John Cremona
Status: needs_reviewpositive_review

Sorry for the delay. I have now successfully installed the spkg and applied the patch (to 4.3.rc0) and everything is working as advertised.

Question: Why the leading underscore in the method _cunningham_prime_factors()? Like this the function does not show up in the reference manual or under normal tab completion, so users will not notice its existence. Since using this is not yet blended in with any other integer factorization code, I fear that people will not genefit from this as much as they might.

As far as I can see the spkg itself has everything that it should. So the positive reivew is for BOTH the inclusion of this as an optional spkg AND for the merging of the patch.

Now I'll go on to look at the patch which depends on this one.

comment:13 Changed 13 years ago by ylchapuy

The name _factor_cunningham was just intended to be like the existing _factor_trial_division.

comment:14 in reply to:  13 Changed 13 years ago by John Cremona

Replying to ylchapuy:

The name _factor_cunningham was just intended to be like the existing _factor_trial_division.

Sure -- but that is used internally by factor() so it is more reasonable to have it hidden from the user. You could add a "use_cunningham" flag to the integer factor function?

comment:15 Changed 13 years ago by Robert Miller

Merged in: 4.3.1.alpha2
Resolution: fixed
Status: positive_reviewclosed

comment:16 Changed 13 years ago by Minh Van Nguyen

Merged in: 4.3.1.alpha2sage-4.3.1.alpha2

comment:17 Changed 13 years ago by Minh Van Nguyen

Is the optional package cunningham_tables-1.0.spkg meant to be in the optional spkg repository at http://www.sagemath.org/packages/optional? I don't see it there at all.

comment:18 in reply to:  17 ; Changed 13 years ago by John Cremona

Replying to mvngu:

Is the optional package cunningham_tables-1.0.spkg meant to be in the optional spkg repository at http://www.sagemath.org/packages/optional? I don't see it there at all.

There's a link to it above: can the release manager take it from there and put it in the correct place?

comment:19 in reply to:  18 Changed 13 years ago by Minh Van Nguyen

Replying to cremona:

There's a link to it above: can the release manager take it from there and put it in the correct place?

Done. See http://www.sagemath.org/packages/optional.

Note: See TracTickets for help on using tickets.