id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
31686,Speed up factoring finite field multiplicative order,gh-daira,,"Initially asked at
- [https://ask.sagemath.org/question/56710 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:
{{{#!python
sage: p = Integer('0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5'
....: 'cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001')
sage: GF(p^2)
}}}
This hangs trying to factor the 891-bit 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 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^2^ - 1 splits as (p-1)(p+1), and factoring those may be much more feasible:
{{{#!python
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.",enhancement,closed,major,sage-9.4,finite rings,fixed,extension-field,slelievre,,"Daira Hopwood, Samuel Lelièvre",Vincent Delecroix,N/A,,8704bb9d9a4391b2487b7027668047997b73f9f4,8704bb9d9a4391b2487b7027668047997b73f9f4,,