Changes between Version 6 and Version 22 of Ticket #31686


Ignore:
Timestamp:
04/25/21 11:35:52 (13 months ago)
Author:
slelievre
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #31686

    • Property Status changed from new to positive_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

  • Ticket #31686 – Description

    v6 v22  
    44
    55There seems to be a unnecessary performance problem with constructing large extension fields:
    6 {{{
    7 sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
     6{{{#!python
     7sage: p = Integer('0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5'
     8....:             'cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001')
    89sage: GF(p^2)
    910}}}
    … …  
    1314
    1415However, 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
     17sage: factor(p - 1)
     182^32 * 3^4 * 17 * 67 * 293 * 349 * 1997 * 19556633 * 44179799701097
     19* 1461985442088199434216480729118540833655826472878315075486478169293801719414121837587283877
     20sage: factor(p + 1)
     212 * 313 * 751 * 2003 * 2671 * 738231097
     22* 55047696457335561580180364861378466840614260303507426009866606293225963076275651294902969015038913167956483928299
    2023}}}
    2124(this takes less than a second on my desktop).