Speed up factoring finite field multiplicative order

[daira]

Initially asked at

• Ask Sage question 56710: Computing the factored multiplicative order of an extension field tries to solve an unnecessarily hard factoring problem

There seems to be a unnecessary performance problem with constructing large extension fields:

sage: p = Integer('0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5'
....:             'cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001')
sage: GF(p^2)

This hangs trying to factor the 891-bit integer p² - 1, which is longer than the longest solved RSA Challenge number. (As it happens, the hard part of this factorization is a 675-bit integer which is still impractical.)

It is not unreasonable that constructing the extension field requires knowing the factorization of the multiplicative order. (You can get around this by constructing it with a specific modulus, but then many operations, e.g. taking roots, require this factorization anyway.)

However, we know that p² - 1 splits as (p-1)(p+1), and factoring those may be much more feasible:

sage: factor(p - 1)
2^32 * 3^4 * 17 * 67 * 293 * 349 * 1997 * 19556633 * 44179799701097
* 1461985442088199434216480729118540833655826472878315075486478169293801719414121837587283877
sage: factor(p + 1)
2 * 313 * 751 * 2003 * 2671 * 738231097
* 55047696457335561580180364861378466840614260303507426009866606293225963076275651294902969015038913167956483928299

(this takes less than a second on my desktop).

In general, computing the multiplicative order of an extension field should take advantage of the factorization of p^k - 1 as a polynomial. There might also be other cases where we know the factorization by construction, and should be able to provide it.

CC: @slel

Component: finite rings

Keywords: extension-field

Author: Daira Hopwood, Samuel Lelièvre

Branch/Commit: 8704bb9

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/31686

[daira]

Changed keywords from none to extension-field

[daira]

comment:2

This appears to work but obviously only addresses the simplest case:

diff --git a/src/sage/rings/finite_rings/finite_field_base.pyx b/src/sage/rings/finite_rings/finite_field_base.pyx
index a4b396621f..6900035193 100644
--- a/src/sage/rings/finite_rings/finite_field_base.pyx
+++ b/src/sage/rings/finite_rings/finite_field_base.pyx
@@ -23,6 +23,7 @@ AUTHORS:
 #       Copyright (C) 2012 Xavier Caruso <xavier.caruso@normalesup.org>
 #       Copyright (C) 2013 Peter Bruin <P.Bruin@warwick.ac.uk>
 #       Copyright (C) 2014 Julian Rueth <julian.rueth@fsfe.org>
+#       Copyright (C) 2021 Daira Hopwood <daira@jacaranda.org>
 #
 #  Distributed under the terms of the GNU General Public License (GPL)
 #  as published by the Free Software Foundation; either version 2 of
@@ -829,7 +830,11 @@ cdef class FiniteField(Field):
             sage: GF(7^2,'a').factored_unit_order()
             (2^4 * 3,)
         """
-        F = (self.order() - 1).factor()
+        if self.degree() == 2:
+            p = self.characteristic()
+            F = (p-1).factor() * (p+1).factor()
+        else:
+            F = (self.order() - 1).factor()
         return (F,)
 
     def cardinality(self):

[sagetrac-tmonteil]

comment:5

For the general case, you can try along the lines:

from sage.structure.factorization import Factorization
p = self.characteristic()
d = self.degree()
x = polygen(ZZ)
F = Factorization([(P(p).factor(), m) for P,m in (x^d-1).factor()]).expand()

Note that for small degrees, it might slow down things, so it might be worth benchmarking first.

[slel]

comment:7

Could cyclotomic_value help?

- F = Factorization([(P(p).factor(), m) for P, m in (x^d - 1).factor()]).expand()
+ F = Factorization([(cyclotomic_value(n, p).factor(), 1)
+                    for n in d.divisors()]).expand()

[videlec]

comment:8

EDIT: I wrongly thought that the program hangs at factoring p^2... this comment is not much relevant to the ticket.

To my mind it is a mistake that GF takes as input p^2 and not the pair (p, 2). I would suggest to

• rework the FiniteFieldFactory to also accept Factorization

sage: p = 17
sage: q = Factorization([[p, 2]])
sage: GF(q)

• tweak the sage preparser so that the p^2 in GF(p^2) is converted to GF(Factorization([[p,2]])).

[videlec]

comment:9

Another example where taking advantage of the cyclotomic factorization does succeed with the proposed fix

sage: p = 1100585370631
sage: GF(p^24)
Finite Field in z24 of size 1100585370631^24

This is a very nice proposal! Coud you submit a branch?

[slel]

comment:10

Please open a ticket to allow GF((p, d)) instead of GF(p^d).

Of course figuring out the prime and degree
when factoring the argument q of GF(q) as p^d
is easier than factoring general composite numbers.
Still it seems a waste that in GF(p^d) the prime power
is computed only to then recover the prime and degree.

[videlec]

comment:11

Replying to @slel:

Please open a ticket to allow GF((p, d)) instead of GF(p^d).

Of course figuring out the prime and degree
when factoring the argument q of GF(q) as p^d
is easier than factoring general composite numbers.
Still it seems a waste that in GF(p^d) the prime power
is computed only to then recover the prime and degree.

This is #31709

[slel]

comment:12

Related:

• Default to random modulus for finite field creation #31434: Default to random modulus for finite field creation

[slel]

comment:13

The attached branch achieves the proposed goal of the ticket,
understood as speeding up (and often allowing at all)
factoring the unit order of non-prime finite fields.

sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
sage: F = GF(p^2, 'a')
sage: F.factored_unit_order()
(2^33 * 3^4 * 17 * 67 * 293 * 313 * 349 * 751
 * 1997 * 2003 * 2671 * 19556633 * 738231097 * 44179799701097
 * 1461985442088199434216480729118540833655826472878315075486478169293801719414121837587283877
 * 55047696457335561580180364861378466840614260303507426009866606293225963076275651294902969015038913167956483928299,)

sage: p = 1100585370631
sage: F = GF(p^24, 'a')
sage: F.factored_unit_order()
(2^6 * 3^2 * 5 * 7 * 11 * 13 * 17 * 53 * 97 * 229 * 337 * 421
 * 3929 * 215417 * 249737 * 262519 * 397897 * 59825761 * 692192057
 * 12506651939 * 37553789761 * 46950147799 * 172462808473 * 434045140817
 * 81866093016401 * 617237859576697 * 659156729361017707
 * 268083135725348991493995910983015600019336657
 * 90433843562394341719266736354746485652016132372842876085423636587989263202299569913,)

Finding a pseudo-Conway polynomial still takes longer
than using a random irreducible polynommial, see #31434.

sage: p = 1100585370631
sage: %time F = GF(p^24, 'a')
CPU times: user 120 ms, sys: 12.3 ms, total: 132 ms
Wall time: 170 ms
sage: %time F = GF(p^24)
CPU times: user 1.76 s, sys: 303 ms, total: 2.07 s
Wall time: 2.46 s

sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
sage: %time F = GF(p^2, 'a')
CPU times: user 1.94 s, sys: 9.62 ms, total: 1.95 s
Wall time: 2.05 s
sage: %time F = GF(p^2)
CPU times: user 14.7 s, sys: 49.9 ms, total: 14.8 s
Wall time: 17.7 s

Please review.

---

New commits:

8704bb9

31686: Use cyclotomics to factor finite field unit order

[slel]

Author: Samuel Lelièvre

[slel]

Branch: public/31686

[slel]

Commit: 8704bb9

[slel]

comment:14

Some questions and thoughts.

I added a doctest in a TESTS block, should it be
in EXAMPLES instead?

I decided to only include a quick one, to keep
doctesting time under control.

Optionally, the example from #31434 and the first
example from here could be added too.

Maybe Flint, NTL, PARI, ... have code we could use
instead of rolling our own?

Should d == 1 and maybe d == 2 be special-cased
to avoid imports in those frequent cases?

[videlec]

comment:15

Replying to @slel:

Some questions and thoughts.

I added a doctest in a TESTS block, should it be
in EXAMPLES instead?

I decided to only include a quick one, to keep
doctesting time under control.

I think this is a good habit.

Optionally, the example from #31434 and the first
example from here could be added too.

If it does not exceed a couple of seconds, why not.

Maybe Flint, NTL, PARI, ... have code we could use
instead of rolling our own?

For PARI/GP

https://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#se:ffprimroot

Should d == 1 and maybe d == 2 be special-cased
to avoid imports in those frequent cases?

I would say yes if it makes a difference in timings.

[roed314]

comment:16

The other suggestion that I'd add is to use factor_cunningham from sage.rings.factorint when p < 12.

[videlec]

comment:17

Replying to @roed314:

The other suggestion that I'd add is to use factor_cunningham from sage.rings.factorint when p < 12.

That might provide a speed up. But in its current state, the package is not usable "optionally" as it lacks a Feature, see #31715.

[videlec]

comment:18

I did not notice any significant speed up by short cutting d=1 or d=2. This ticket provides a great improvement!

[videlec]

Reviewer: Vincent Delecroix

[slel]

comment:19

Please @daira add your full name in the author field.

[videlec]

Changed author from Samuel Lelièvre to Daira Hopwood, Samuel Lelièvre

[videlec]

comment:21

(from https://github.com/daira)

[daira]

comment:23

Yes that's my name. Thankyou all for being so responsive to this ticket! :-)

[vbraun]

Changed branch from public/31686 to 8704bb9