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)

trac7240_make_standard.patch (902 bytes) - added by ylchapuy 10 years ago.
trac7240_Cunningham_factorization_application.patch (4.6 KB) - added by ylchapuy 9 years ago.
rebased on sage 4.4
7240.patch (34.2 KB) - added by roed 7 years ago.

Download all attachments as: .zip

Change History (55)

comment:1 Changed 10 years ago by ylchapuy

  • Authors set to Yann Laigle-Chapuy
  • 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 ylchapuy

  • Status changed from new to needs_review

comment:3 Changed 10 years ago by AlexGhitza

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

  • Report Upstream set to N/A
  • Reviewers set to John Cremona
  • Status changed from needs_review to needs_work

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.

comment:5 Changed 10 years ago by ylchapuy

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 cremona

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 ylchapuy

This ticket is marked as "needs work", but what should be done exactly?

comment:8 Changed 10 years ago by cremona

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

  • Status changed from needs_review to positive_review

comment:10 Changed 10 years ago by mvngu

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: Changed 10 years ago by 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!

comment:12 in reply to: ↑ 11 Changed 10 years ago by mvngu

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:

  1. the (currently optional) Cunningham package becomes a standard spkg; or
  2. there is some code to test whether that spkg is installed.

Changed 10 years ago by ylchapuy

comment:13 Changed 10 years ago by ylchapuy

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: Changed 10 years ago by 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?

I have written myself a PARI/GP-2.4 script which

1) tries to determine which bn-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 10555-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 bn-1 to the database (larger b and n).

comment:15 in reply to: ↑ 14 Changed 10 years ago by ylchapuy

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 was

  • Status changed from positive_review to needs_work

Changed 9 years ago by ylchapuy

rebased on sage 4.4

comment:17 Changed 9 years ago by ylchapuy

  • Status changed from needs_work to needs_review

I think it's ok for review now.

comment:18 Changed 9 years ago by ylchapuy

(again...) and it should be ok without the spkg.

comment:19 Changed 9 years ago by jdemeyer

  • Component changed from algebra to factorization

comment:20 Changed 9 years ago by jdemeyer

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 cremona

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 jdemeyer

  • Status changed from needs_review to needs_work

It's still in my TODO list.

comment:23 Changed 9 years ago by roed

As encouragement for working on this ticket, I'm using _factor_cunningham in #7931. Now that #8334 has a positive review, #7931 is ready to review, but it's getting doctest failures because of the warning generated by _factor_cunningham.

comment:24 Changed 8 years ago by roed

Any progress on this ticket? I'd like to use it in #8335.

comment:25 Changed 8 years ago by roed

  • Authors changed from Yann Laigle-Chapuy to Yann Laigle-Chapuy, David Roe
  • 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 roed

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 roed

  • Dependencies #12117 deleted
  • Owner changed from tbd to roed

comment:28 Changed 8 years ago by roed

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 roed

  • Dependencies set to #12133

comment:30 Changed 8 years ago by roed

  • Dependencies #12133 deleted

comment:31 Changed 8 years ago by ohanar

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

  • Reviewers changed from John Cremona to John Cremona, R. Andrew Ohana

comment:33 Changed 7 years ago by jpflori

  • Cc jpflori added

comment:34 Changed 7 years ago by roed

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

comment:35 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:36 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:37 Changed 6 years ago by rws

  • Dependencies set to #15813

comment:38 Changed 6 years ago by rws

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

Last edited 6 years ago by rws (previous) (diff)

comment:39 Changed 6 years ago by rws

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 rws

  • Dependencies #15813 deleted

comment:41 Changed 6 years ago by rws

  • Owner changed from roed to rws

comment:42 in reply to: ↑ 11 Changed 6 years ago by jpflori

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: Changed 6 years ago by jpflori

(And note that the data provided should surely be updated.)

comment:44 in reply to: ↑ 43 Changed 6 years ago by rws

Replying to jpflori:

(And note that the data provided should surely be updated.)

But don't use $SAGE_DATA anymore, use $SAGE_SHARE or $SAGE_ROOT/share, see #15814

comment:45 Changed 6 years ago by rws

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

  • Commit set to 535749ae30dd83feac91fdaae963a189f63f4e43
  • Dependencies set to #15813
  • Status changed from needs_work to needs_review

Separated from the SPKG install (#15813) and rebased on 6.2.base2.


New commits:

535749aTrac #7240: cunningham numbers factorization applications

comment:47 Changed 5 years ago by rws

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

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

  • Authors changed from Yann Laigle-Chapuy, David Roe to Yann Laigle-Chapuy, David Roe, Ralf Stephan
  • Commit changed from 535749ae30dd83feac91fdaae963a189f63f4e43 to b0cb5241d1175453dde38ea8044e3e0fcd6956cf
  • Status changed from needs_work to needs_review

Rebase on 6.2.beta6. Fix failing doctests.


New commits:

cf2c6baMerge branch 'u/rws/ticket/7240' of ssh://trac.sagemath.org/sage into needswork/7240
b0cb524Trac 7240: don't beg user to install tables; fail gracefully if not installed

comment:50 Changed 5 years ago by rws

  • Milestone changed from sage-6.2 to sage-pending

comment:51 Changed 5 years ago by rws

  • Status changed from needs_review to needs_work

comment:52 Changed 20 months ago by rws

  • Dependencies changed from #15813 to #12133
Note: See TracTickets for help on using tickets.