Changes between Version 6 and Version 22 of Ticket #31686
- Timestamp:
- 04/25/21 11:35:52 (13 months ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Ticket #31686
-
Property
Status
changed from
new
topositive_review
-
Property
Reviewers
changed from
to
Vincent Delecroix
-
Property
Authors
changed from
to
Daira Hopwood, Samuel Lelièvre
-
Property
Branch
changed from
to
public/31686
-
Property
Commit
changed from
to
8704bb9d9a4391b2487b7027668047997b73f9f4
-
Property
Status
changed from
-
Ticket #31686 – Description
v6 v22 4 4 5 5 There seems to be a unnecessary performance problem with constructing large extension fields: 6 {{{ 7 sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001 6 {{{#!python 7 sage: p = Integer('0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5' 8 ....: 'cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001') 8 9 sage: GF(p^2) 9 10 }}} … … 13 14 14 15 However, we know that p^2^ - 1 splits as (p-1)(p+1), and factoring those may be much more feasible: 15 {{{ 16 sage: factor(p-1) 17 2^32 * 3^4 * 17 * 67 * 293 * 349 * 1997 * 19556633 * 44179799701097 * 1461985442088199434216480729118540833655826472878315075486478169293801719414121837587283877 18 sage: factor(p+1) 19 2 * 313 * 751 * 2003 * 2671 * 738231097 * 55047696457335561580180364861378466840614260303507426009866606293225963076275651294902969015038913167956483928299 16 {{{#!python 17 sage: factor(p - 1) 18 2^32 * 3^4 * 17 * 67 * 293 * 349 * 1997 * 19556633 * 44179799701097 19 * 1461985442088199434216480729118540833655826472878315075486478169293801719414121837587283877 20 sage: factor(p + 1) 21 2 * 313 * 751 * 2003 * 2671 * 738231097 22 * 55047696457335561580180364861378466840614260303507426009866606293225963076275651294902969015038913167956483928299 20 23 }}} 21 24 (this takes less than a second on my desktop).