Revision history [back]

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.

It is not unreasonable that constructing the extension field requires knowing the multiplicative order. (You can get around this by constructing it with a specific modulus, but then many operations, e.g. taking roots, require the order 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.

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.

It is not unreasonable that constructing the extension field requires knowing the multiplicative order. (You can get around this by constructing it with a specific modulus, but then many operations, e.g. taking roots, require the order 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.

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.

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 the order 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.polynomial. There might also be other cases where we know the factorization by construction, and should be able to provide it.

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.

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.

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

sage: p = 0x24000000000024000130e0000d7f70e4a803ca76f439266f443f9a5cda8a6c7be4a7a5fe8fadffd6a2a7e8c30006b9459ffffcd300000001
 sage: GF(p^2)
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.

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.

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.

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.

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.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.

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.

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.