On Dec 9, 2011 10:00 AM, "David Roe" <r...@math.harvard.edu> wrote:
>
> I'd like to propose making the Cunningham Tables spkg standard.
>
> == BASIC DETAILS ==
>
> It contains factorizations for integers of the form b^k + 1 and b^k -
> 1, with b in {2, 3, 5, 6, 7, 10, 11, 12}.
> It has been an optional spkg for a couple of years. The total size is
1.1 MB.
>
> Ticket #7240 updates the spkg to version 2.0 and updates the Sage
> library to interface with a changed data format.
> Ticket #12125 adds integer factoring methods to take advantage of the new
data.
>
> == APPLICATIONS ==
>
> After a couple seconds loading a dictionary into memory
Is it really a *couple of second*?
> the first time
> it's needed, we have the following timings. I don't list comparisons
> to sage-4.7.2 since these factorizations aren't very feasible without
> the Cunningham tables.
>
> sage: n = 2^341 + 1
> sage: timeit("F = factor(n)")
> 625 loops, best of 3: 38.7 µs per loop
> sage: n = 12^600 - 1
> sage: timeit("F = factor(n)")
> 625 loops, best of 3: 149 µs per loop
>
> There are also routines for fast partial factorizations:
>
> sage: n = 11^4800 - 1
> sage: from sage.rings.factorint import factor_power_pm_1
> sage: F = factor_power_pm_1(None, 11, 4800, -1)
> sage: len(F)
> 112
> sage: [p.is_pseudoprime() for p, _ in F].count(False)
> 6
> sage: timeit("F = factor_power_pm_1(None, 11, 4800, -1)")
> 25 loops, best of 3: 10.7 ms per loop
>
> Having fast factorizations for numbers of this form is useful when
> working with finite fields (computing nth roots in finite fields of
> small characteristic for example).
>
> == VOTE! ==
>
> The tickets need review, but to include a new SPKG in Sage we also
> need a vote. So please vote for
> [ ] Make cunningham_tables-2.0.spkg standard
> [ ] Update from cunningham_tables-1.0 to 2.0, but leave it as optional.
>
> == BEYOND BASE 12 ==
>
> On a related note, I've created a new SPKG wrapping Richard Brent's
> factor tables, which include partial information for bases up to 9998.
> It's 11.2 MB, and I'm proposing making it an optional spkg. After
> installing it and applying #12133, the timing difference with magma
> for factoring 103^100 - 1 (pointed out at
>
http://groups.google.com/group/sage-devel/browse_thread/thread/8fc9304114a62015
)
> is resolved:
>
> sage: timeit("F = factor(103^100-1)")
> 5 loops, best of 3: 60 ms per loop
>
> David
>
> --
> To post to this group, send an email to sage-devel@googlegroups.com
> To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
> For more options, visit this group at
http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
