Opened 9 months ago
Closed 8 months ago
#31686 closed enhancement (fixed)
Speed up factoring finite field multiplicative order
Reported by:  ghdaira  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  finite rings  Keywords:  extensionfield 
Cc:  slelievre  Merged in:  
Authors:  Daira Hopwood, Samuel Lelièvre  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  8704bb9 (Commits, GitHub, GitLab)  Commit:  8704bb9d9a4391b2487b7027668047997b73f9f4 
Dependencies:  Stopgaps: 
Description (last modified by )
Initially asked at
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 891bit integer p^{2}  1, which is longer than the longest solved RSA Challenge number. (As it happens, the hard part of this factorization is a 675bit 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^{2}  1 splits as (p1)(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.
Change History (24)
comment:1 Changed 9 months ago by
 Component changed from PLEASE CHANGE to number theory
 Keywords extensionfield added
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 9 months ago by
comment:3 Changed 9 months ago by
 Description modified (diff)
comment:4 Changed 9 months ago by
 Description modified (diff)
comment:5 Changed 9 months ago by
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^d1).factor()]).expand()
Note that for small degrees, it might slow down things, so it might be worth benchmarking first.
comment:6 Changed 9 months ago by
 Cc slelievre added
 Component changed from number theory to finite rings
 Description modified (diff)
 Summary changed from Computing the factored multiplicative order of an extension field tries to solve an unnecessarily hard factoring problem to Speed up factoring finite field multiplicative order
comment:7 Changed 9 months ago by
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()
comment:8 Changed 9 months ago by
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 acceptFactorization
sage: p = 17 sage: q = Factorization([[p, 2]]) sage: GF(q)
 tweak the sage preparser so that the
p^2
inGF(p^2)
is converted toGF(Factorization([[p,2]]))
.
comment:9 Changed 9 months ago by
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?
comment:10 followup: ↓ 11 Changed 9 months ago by
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.
comment:11 in reply to: ↑ 10 Changed 9 months ago by
Replying to slelievre:
Please open a ticket to allow
GF((p, d))
instead ofGF(p^d)
.Of course figuring out the prime and degree when factoring the argument
q
ofGF(q)
asp^d
is easier than factoring general composite numbers. Still it seems a waste that inGF(p^d)
the prime power is computed only to then recover the prime and degree.
This is #31709
comment:12 Changed 9 months ago by
Related:
 #31434: Default to random modulus for finite field creation
comment:13 Changed 9 months ago by
 Branch set to public/31686
 Commit set to 8704bb9d9a4391b2487b7027668047997b73f9f4
 Status changed from new to needs_review
The attached branch achieves the proposed goal of the ticket, understood as speeding up (and often allowing at all) factoring the unit order of nonprime 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 pseudoConway 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

comment:14 followup: ↓ 15 Changed 9 months ago by
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 specialcased
to avoid imports in those frequent cases?
comment:15 in reply to: ↑ 14 Changed 9 months ago by
Replying to slelievre:
Some questions and thoughts.
I added a doctest in a
TESTS
block, should it be inEXAMPLES
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.ubordeaux.fr/dochtml/html/Arithmetic_functions.html#se:ffprimroot
Should
d == 1
and maybed == 2
be specialcased to avoid imports in those frequent cases?
I would say yes if it makes a difference in timings.
comment:16 followup: ↓ 17 Changed 9 months ago by
The other suggestion that I'd add is to use factor_cunningham
from sage.rings.factorint
when p < 12
.
comment:17 in reply to: ↑ 16 Changed 9 months ago by
comment:18 Changed 9 months ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
I did not notice any significant speed up by short cutting d=1
or d=2
. This ticket provides a great improvement!
comment:19 Changed 9 months ago by
Please @ghdaira add your full name in the author field.
comment:20 Changed 9 months ago by
comment:21 Changed 9 months ago by
(from https://github.com/daira)
comment:22 Changed 9 months ago by
 Description modified (diff)
comment:23 Changed 9 months ago by
Yes that's my name. Thankyou all for being so responsive to this ticket! :)
comment:24 Changed 8 months ago by
 Branch changed from public/31686 to 8704bb9d9a4391b2487b7027668047997b73f9f4
 Resolution set to fixed
 Status changed from positive_review to closed
This appears to work but obviously only addresses the simplest case: