ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 21 Apr 2021 11:40:21 +0200Computing the factored multiplicative order of an extension field tries to solve an unnecessarily hard factoring problemhttps://ask.sagemath.org/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:
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.Sun, 18 Apr 2021 12:48:15 +0200https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/Comment by slelievre for <p>There seems to be a unnecessary performance problem with constructing large extension fields:</p>
<pre><code>sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
sage: GF(p^2)
</code></pre>
<p>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.)</p>
<p>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.)</p>
<p>However, we know that $p^2 - 1$ splits as $(p-1)(p+1)$, and factoring those may be much more feasible:</p>
<pre><code>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
</code></pre>
<p>(this takes less than a second on my desktop).</p>
<p>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.</p>
https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?comment=56752#post-id-56752See also related ticket:
- [Sage Trac ticket 31434: Default to random modulus for finite field creation](https://trac.sagemath.org/ticket/31434)Wed, 21 Apr 2021 11:40:21 +0200https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?comment=56752#post-id-56752Comment by slelievre for <p>There seems to be a unnecessary performance problem with constructing large extension fields:</p>
<pre><code>sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
sage: GF(p^2)
</code></pre>
<p>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.)</p>
<p>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.)</p>
<p>However, we know that $p^2 - 1$ splits as $(p-1)(p+1)$, and factoring those may be much more feasible:</p>
<pre><code>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
</code></pre>
<p>(this takes less than a second on my desktop).</p>
<p>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.</p>
https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?comment=56715#post-id-56715Excellent idea. Please open a ticket!Sun, 18 Apr 2021 17:20:56 +0200https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?comment=56715#post-id-56715Answer by tmonteil for <p>There seems to be a unnecessary performance problem with constructing large extension fields:</p>
<pre><code>sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
sage: GF(p^2)
</code></pre>
<p>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.)</p>
<p>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.)</p>
<p>However, we know that $p^2 - 1$ splits as $(p-1)(p+1)$, and factoring those may be much more feasible:</p>
<pre><code>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
</code></pre>
<p>(this takes less than a second on my desktop).</p>
<p>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.</p>
https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?answer=56712#post-id-56712Thanks for the remark. If you want to contribute to Sage code, you could have a look to https://www.sagemath.org/development.html request for a trac account and create a ticket. Do not hesitate to ask for more details.
Sun, 18 Apr 2021 13:34:51 +0200https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?answer=56712#post-id-56712Comment by tmonteil for <p>Thanks for the remark. If you want to contribute to Sage code, you could have a look to <a href="https://www.sagemath.org/development.html">https://www.sagemath.org/development....</a> request for a trac account and create a ticket. Do not hesitate to ask for more details.</p>
https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?comment=56722#post-id-56722Great, thanks !Sun, 18 Apr 2021 21:39:13 +0200https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?comment=56722#post-id-56722Comment by daira for <p>Thanks for the remark. If you want to contribute to Sage code, you could have a look to <a href="https://www.sagemath.org/development.html">https://www.sagemath.org/development....</a> request for a trac account and create a ticket. Do not hesitate to ask for more details.</p>
https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?comment=56721#post-id-56721Done: https://trac.sagemath.org/ticket/31686Sun, 18 Apr 2021 20:23:56 +0200https://ask.sagemath.org/question/56710/computing-the-factored-multiplicative-order-of-an-extension-field-tries-to-solve-an-unnecessarily-hard-factoring-problem/?comment=56721#post-id-56721