Ask Your Question

Computing the factored multiplicative order of an extension field tries to solve an unnecessarily hard factoring problem

asked 2021-04-18 12:48:15 +0200

daira gravatar image

updated 2021-05-02 21:56:19 +0200

tmonteil gravatar image

There seems to be a unnecessary performance problem with constructing large extension fields:

sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
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:

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.

edit retag flag offensive close merge delete


Excellent idea. Please open a ticket!

slelievre gravatar imageslelievre ( 2021-04-18 17:20:56 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2021-04-18 13:34:51 +0200

tmonteil gravatar image

Thanks for the remark. If you want to contribute to Sage code, you could have a look to request for a trac account and create a ticket. Do not hesitate to ask for more details.

edit flag offensive delete link more


daira gravatar imagedaira ( 2021-04-18 20:23:56 +0200 )edit

Great, thanks !

tmonteil gravatar imagetmonteil ( 2021-04-18 21:39:13 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-04-18 12:48:15 +0200

Seen: 52 times

Last updated: Apr 18