Opened 10 years ago
Last modified 20 months ago
#7240 needs_work enhancement
factorization of Cunningham numbers - applications
Reported by: | ylchapuy | Owned by: | rws |
---|---|---|---|
Priority: | major | Milestone: | sage-pending |
Component: | factorization | Keywords: | |
Cc: | jpflori, rws | Merged in: | |
Authors: | Yann Laigle-Chapuy, David Roe, Ralf Stephan | Reviewers: | John Cremona, R. Andrew Ohana |
Report Upstream: | N/A | Work issues: | |
Branch: | public/cunninghamtables (Commits) | Commit: | b0cb5241d1175453dde38ea8044e3e0fcd6956cf |
Dependencies: | #12133 | Stopgaps: |
Description
Following #7239, use the factorization of Cunningham numbers to speed up polynomial primitivity testing and other finite field stuff (for small characteristic).
Attachments (3)
Change History (55)
comment:1 Changed 10 years ago by
- Milestone set to sage-4.2
- Summary changed from factorization of Cunningham numbers - applications to [with patch, needs review] factorization of Cunningham numbers - applications
comment:2 Changed 10 years ago by
- Status changed from new to needs_review
comment:3 Changed 10 years ago by
- Summary changed from [with patch, needs review] factorization of Cunningham numbers - applications to factorization of Cunningham numbers - applications
comment:4 Changed 10 years ago by
- Report Upstream set to N/A
- Reviewers set to John Cremona
- Status changed from needs_review to needs_work
comment:5 Changed 10 years ago by
In fact if the patch from #7239 is applied, but the database not installed, _factor_cunningham
will just be the usual factor, with the first time it's called a warning (not an error) saying:
"You might consider installing the optional package for factoring Cunningham numbers with the following command: sage -i cunningham_tables-1.0
"
Moreover this warning will only be seen if the characteristic is p \in {2,3,5,7,11}
and p^k > 2^100
. I thought it was nice to tell the user that there exists an optional package useful for them, but I can remove it if necessary.
comment:6 Changed 10 years ago by
OK, that is more reasonable. But why don't we (you!) put a case to sage-devel for including this spkg as standard? It's only another 492837 bytes, and the cremona database is 78M.
comment:7 Changed 10 years ago by
This ticket is marked as "needs work", but what should be done exactly?
comment:8 Changed 10 years ago by
- Status changed from needs_work to needs_review
I set it to "needs work" but then agreed that it was good (but did not change the label). On the other hand, there has been discussion on sage-devel in favour of including this as standard anyway.
So I suggest that we give this a positive review. This will take two steps....
comment:9 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:10 Changed 10 years ago by
After applying the attachment trac7240_Cunningham_factorization_application.patch, I got the following doctest failures on Sage 4.3.1. In all of these cases, I didn't install the optional Cunningham spkg at #7239
[mvngu@sage sage-4.3.1]$ ./sage -t -long devel/sage-main/sage/rings/finite_field_ntl_gf2e.pyx sage -t -long "devel/sage-main/sage/rings/finite_field_ntl_gf2e.pyx" ********************************************************************** File "/mnt/usb1/scratch/mvngu/release/sage-4.3.1/devel/sage-main/sage/rings/finite_field_ntl_gf2e.pyx", line 1349: sage: b._gap_init_() Expected: 'Z(65536)^1' Got: doctest:21: UserWarning: You might consider installing the optional package for factoring Cunningham numbers with the following command: ``sage -i cunningham_tables-1.0`` 'Z(65536)^1' [mvngu@sage sage-4.3.1]$ ./sage -t -long devel/sage-main/sage/rings/finite_field_element.py sage -t -long "devel/sage-main/sage/rings/finite_field_element.py" ********************************************************************** File "/mnt/usb1/scratch/mvngu/release/sage-4.3.1/devel/sage-main/sage/rings/finite_field_element.py", line 375: sage: a.multiplicative_order() Expected: 124 Got: doctest:21: UserWarning: You might consider installing the optional package for factoring Cunningham numbers with the following command: ``sage -i cunningham_tables-1.0`` 124 [mvngu@sage sage-4.3.1]$ ./sage -t -long devel/sage-main/sage/rings/finite_field_ext_pari.py sage -t -long "devel/sage-main/sage/rings/finite_field_ext_pari.py" ********************************************************************** File "/mnt/usb1/scratch/mvngu/release/sage-4.3.1/devel/sage-main/sage/rings/finite_field_ext_pari.py", line 103: sage: z.multiplicative_order() Expected: 15 Got: doctest:21: UserWarning: You might consider installing the optional package for factoring Cunningham numbers with the following command: ``sage -i cunningham_tables-1.0`` 15 [mvngu@sage sage-4.3.1]$ ./sage -t -long devel/sage-main/sage/rings/polynomial/polynomial_element.pyx sage -t -long "devel/sage-main/sage/rings/polynomial/polynomial_element.pyx" ********************************************************************** File "/mnt/usb1/scratch/mvngu/release/sage-4.3.1/devel/sage-main/sage/rings/polynomial/polynomial_element.pyx", line 2860: sage: f.is_irreducible(), f.is_primitive() Expected: (True, False) Got: doctest:21: UserWarning: You might consider installing the optional package for factoring Cunningham numbers with the following command: ``sage -i cunningham_tables-1.0`` (True, False) [mvngu@sage sage-4.3.1]$ ./sage -t -long devel/sage-main/sage/groups/generic.py sage -t -long "devel/sage-main/sage/groups/generic.py" ********************************************************************** File "/mnt/usb1/scratch/mvngu/release/sage-4.3.1/devel/sage-main/sage/groups/generic.py", line 774: sage: discrete_log(u,g) Expected: 123456789 Got: doctest:21: UserWarning: You might consider installing the optional package for factoring Cunningham numbers with the following command: ``sage -i cunningham_tables-1.0`` 123456789
comment:11 follow-ups: ↓ 12 ↓ 42 Changed 10 years ago by
I think my positive review was dependent on the vote we had (yes we did!) to include the spkg as standard rather then optional -- it is very small and requires no building. The spkg is attached to (sorry, linked to) the ticket #7239. I'm sure I assumed that when that ticket was closed, the right thing would happen to its spkg!
comment:12 in reply to: ↑ 11 Changed 10 years ago by
Replying to cremona:
I think my positive review was dependent on the vote we had (yes we did!) to include the spkg as standard rather then optional
Thank you for the clarification, John. The merging of this ticket can wait until:
- the (currently optional) Cunningham package becomes a standard spkg; or
- there is some code to test whether that spkg is installed.
Changed 10 years ago by
comment:13 Changed 10 years ago by
This is of course all my fault. I stated that the warning wouldn't appear for numbers of less than 100 bits, but it was not the case. I updated the patch, switching two lines and it should be fine now. At least for me the above failures disappear.
The second patch I added is what should be done if the package become standard (and yes we had a vote, what's the next step?). It replaces my warning/advertisment with an error.
Yann
comment:14 follow-up: ↓ 15 Changed 10 years ago by
Dear everyone,
I would like to add a few comments here. If I understand things correctly, the Cunningham database in SAGE is now just a list of numbers without structure, right?
I have written myself a PARI/GP-2.4 script which
1) tries to determine which b^{n}-1 numbers have a non-trivial gcd with a given number. The algorithm is essentially p-1 factorisation, but with several well-chosen bases instead of one (random) base.
2) uses that information to do Aurifeuillian factorisation and a more clever table lookup.
Step 1) can be skipped if we know exactly that we want to factor 10^{555-1 for example. }
I could probably manage to port this to some SAGE functions in Python. Once this has been done, I would like to add a lot more factors to more numbers of the form b^{n-1 to the database (larger b and n). }
comment:15 in reply to: ↑ 14 Changed 10 years ago by
Replying to jdemeyer:
Dear everyone,
I would like to add a few comments here. If I understand things correctly, the Cunningham database in SAGE is now just a list of numbers without structure, right?
Yes right, this was just a quick and dirty solution to my problems.
I have written myself a PARI/GP-2.4 script (snip) I could probably manage to port this to some SAGE functions in Python. (snip)
This would be great if you port your work to SAGE. My first thought was to include your script but currently SAGE is still shipping pari 2.3.3.
Yann
comment:16 Changed 9 years ago by
- Status changed from positive_review to needs_work
comment:17 Changed 9 years ago by
- Status changed from needs_work to needs_review
I think it's ok for review now.
comment:18 Changed 9 years ago by
(again...) and it should be ok without the spkg.
comment:19 Changed 9 years ago by
- Component changed from algebra to factorization
comment:20 Changed 9 years ago by
I plan to work on this and improve it a lot. In particular, the database of Cunningham factors should not be just a list, it should know of which numbers the factors are factors of (i.e. factor p divides Phi_a(b))
comment:21 Changed 9 years ago by
This is one of the tickets which the Sage nagbot regularly nags me about. But anyone seeing Jeroen's last comment will wait rather than review it. I suggest that *either* this patch gets reviewed as is, and Jeroen's improvements go on another ticket, *or* the "needs review" tag is changed to "needs work".
comment:22 Changed 9 years ago by
- Status changed from needs_review to needs_work
It's still in my TODO list.
comment:23 Changed 9 years ago by
comment:24 Changed 8 years ago by
Any progress on this ticket? I'd like to use it in #8335.
comment:25 Changed 8 years ago by
- Dependencies set to #12117
- Status changed from needs_work to needs_review
This patch accompanies a new spkg: http://sage.math.washington.edu/home/roed/cunningham_tables-2.0.spkg.
Apply 7240.patch only.
comment:26 Changed 8 years ago by
Also, this patch assumes that the Cunningham tables spkg has been made standard. I'll e-mail sage-devel about that soon.
comment:27 Changed 8 years ago by
- Dependencies #12117 deleted
- Owner changed from tbd to roed
comment:28 Changed 8 years ago by
There's a new version of the spkg at: Cunningham_Tables-2.1. This new version will only work after applying #12133.
comment:29 Changed 8 years ago by
- Dependencies set to #12133
comment:30 Changed 8 years ago by
- Dependencies #12133 deleted
comment:31 Changed 8 years ago by
- Status changed from needs_review to needs_work
please make sure that both sobj's use python ints (and longs) and not sage integers. Also remove the trailing whitespace in
- docstring for FiniteField?.factored_order
- docstring for Polynomial.is_primitive
- docstring for CunninghamDatabase?
- "x is not a list" line in cunningham_database.py
Finally, it would be great if you would make your error's python 3 compatible, since we should probably start thinking forward to the day we make that transition.
comment:32 Changed 8 years ago by
- Reviewers changed from John Cremona to John Cremona, R. Andrew Ohana
comment:33 Changed 7 years ago by
- Cc jpflori added
comment:34 Changed 7 years ago by
- Status changed from needs_work to needs_review
I've addressed Andrew's comments, and added a new version of the SPKG at http://sage.math.washington.edu/home/roed/cunningham_tables-2.2.spkg
Changed 7 years ago by
comment:35 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:36 Changed 6 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:37 Changed 6 years ago by
- Dependencies set to #15813
comment:38 Changed 6 years ago by
- Cc rws added
- Status changed from needs_review to needs_work
Your file 7240.patch
tries to upgrade the cunningham_table
package to 2.2 which isn't what is advertised with this ticket. Please don't do this, it makes difficult things even more so.
I suppose then that the patch to be reviewed would be the one by @ylchapuy named trac7240_Cunningham_factorization_application.patch
. Even with the -l
option it fails to apply with Sage-6.0.
comment:39 Changed 6 years ago by
From the sage developer's guide:
If a function requires an optional package, that function should fail gracefully—perhaps using a try-except block—when the optional package is not available, and should give a hint about how to install it. ...
comment:40 Changed 6 years ago by
- Dependencies #15813 deleted
comment:41 Changed 6 years ago by
- Owner changed from roed to rws
comment:42 in reply to: ↑ 11 Changed 6 years ago by
Replying to cremona:
I think my positive review was dependent on the vote we had (yes we did!) to include the spkg as standard rather then optional -- it is very small and requires no building. The spkg is attached to (sorry, linked to) the ticket #7239. I'm sure I assumed that when that ticket was closed, the right thing would happen to its spkg!
It was voted that the new cunningham package would become standard.
comment:43 follow-up: ↓ 44 Changed 6 years ago by
(And note that the data provided should surely be updated.)
comment:44 in reply to: ↑ 43 Changed 6 years ago by
comment:45 Changed 6 years ago by
- Branch set to u/rws/ticket/7240
- Modified changed from 02/14/14 08:48:54 to 02/14/14 08:48:54
comment:46 Changed 6 years ago by
- Commit set to 535749ae30dd83feac91fdaae963a189f63f4e43
- Dependencies set to #15813
- Status changed from needs_work to needs_review
comment:47 Changed 5 years ago by
- Status changed from needs_review to needs_work
patchbot reports failures in rings/
and groups/
: among others ImportError: cannot import name CunninghamDatabase
. Of course the patchbot will test without the package being installed, so it made sense what I wrote in comment:39 about failing gracefully...
comment:48 Changed 5 years ago by
- Branch changed from u/rws/ticket/7240 to public/cunninghamtables
- Modified changed from 04/04/14 14:06:08 to 04/04/14 14:06:08
comment:49 Changed 5 years ago by
- Commit changed from 535749ae30dd83feac91fdaae963a189f63f4e43 to b0cb5241d1175453dde38ea8044e3e0fcd6956cf
- Status changed from needs_work to needs_review
comment:50 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-pending
comment:51 Changed 5 years ago by
- Status changed from needs_review to needs_work
comment:52 Changed 20 months ago by
- Dependencies changed from #15813 to #12133
The patch applies fine to 4.3.rc0 after installing the optional spkg at #7239 and the patch there, and tests pass. Good doctests included.
BUT in both places where _cunningham_prime_factors() is called, a run-time error will be raised if the optional database is not installed. If the database is really going to be optional then these calls must be wrapped with try/except, otherwise people who have not installed the optional package will find lots of their code fails.
Hence: needs work.