Changes between Initial Version and Version 3 of Ticket #31686


Ignore:
Timestamp:
04/18/21 18:51:30 (13 months ago)
Author:
gh-daira
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #31686

    • Property Keywords extension-field added
    • Property Component changed from PLEASE CHANGE to number theory
    • Property Type changed from PLEASE CHANGE to enhancement
  • Ticket #31686 – Description

    initial v3  
    22
    33There seems to be a unnecessary performance problem with constructing large extension fields:
    4 
     4{{{
    55    sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
    66    sage: GF(p^2)
    7 
     7}}}
    88This 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.)
    99
     
    1111
    1212However, we know that p^2^ - 1 splits as (p-1)(p+1), and factoring those may be much more feasible:
    13 
     13{{{
    1414    sage: factor(p-1)                                                                                                                                                 
    1515    2^32 * 3^4 * 17 * 67 * 293 * 349 * 1997 * 19556633 * 44179799701097 * 1461985442088199434216480729118540833655826472878315075486478169293801719414121837587283877
    1616    sage: factor(p+1)                                                                                                                                                 
    1717    2 * 313 * 751 * 2003 * 2671 * 738231097 * 55047696457335561580180364861378466840614260303507426009866606293225963076275651294902969015038913167956483928299
    18 
     18}}}
    1919(this takes less than a second on my desktop).
    2020