#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: |
Description (last modified by )
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)
Change History (20)
comment:1 Changed 13 years ago by
comment:2 Changed 13 years ago by
Description: | modified (diff) |
---|---|
Summary: | factorization of Cunningham numbers → factorization of Cunningham numbers [with patch and spkg, needs review] |
comment:3 Changed 13 years ago by
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
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
Status: | new → needs_review |
---|
comment:6 Changed 13 years ago by
Report Upstream: | → N/A |
---|---|
Status: | needs_review → needs_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
Status: | needs_work → needs_review |
---|---|
Summary: | [with patch and spkg, needs review] factorization of Cunningham numbers → factorization 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
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 follow-up: 11 Changed 13 years ago by
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
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 Changed 13 years ago by
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
Keywords: | integer factorization Cunningham added |
---|---|
Reviewers: | → John Cremona |
Status: | needs_review → positive_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 follow-up: 14 Changed 13 years ago by
The name _factor_cunningham
was just intended to be like the existing _factor_trial_division
.
comment:14 Changed 13 years ago by
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
Merged in: | → 4.3.1.alpha2 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:16 Changed 13 years ago by
Merged in: | 4.3.1.alpha2 → sage-4.3.1.alpha2 |
---|
comment:17 follow-up: 18 Changed 13 years ago by
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 follow-up: 19 Changed 13 years ago by
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 Changed 13 years ago by
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.
The package is here: http://yann.laiglechapuy.net/spkg/cunningham_tables-1.0.spkg