Revision history [back]

I made a computation involving the computation of a Groebner basis under a finite field of large characteristic $p$.

If $p<2^{31}$ then everything is ok:

sage: %time function(previous_prime(2^31))
CPU times: user 875 ms, sys: 31 ms, total: 906 ms
Wall time: 1.14 s
[1]

But if $p>2^{31}$ then the computation became very slow:

sage: %time function(next_prime(2^31))
verbose 0 (3837: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.

I guess that it has something to do with 32-bits computer integers. The point is that my computer is 64-bits.

Question: Is there a way to avoid this slow-down (at least for $p<2^{63}$)?

I made a computation involving the computation of a Groebner basis under a finite field of large characteristic $p$.

If $p<2^{31}$ then everything is ok:

sage: %time function(previous_prime(2^31))
CPU times: user 875 ms, sys: 31 ms, total: 906 ms
Wall time: 1.14 s
[1]

But if $p>2^{31}$ then the computation became very slow:

sage: %time function(next_prime(2^31))
verbose 0 (3837: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.

I guess that it has something to do with 32-bits computer integers. The point is that my computer is 64-bits.

Question: Is there a way to avoid this slow-down (at least for $p<2^{63}$)?

I made a computation involving the computation of a Groebner basis under a finite field of large characteristic $p$.

If $p<2^{31}$ then everything is ok:

sage: %time function(previous_prime(2^31))
CPU times: user 875 ms, sys: 31 ms, total: 906 ms
Wall time: 1.14 s
[1]

But if $p>2^{31}$ then the computation became very slow:

sage: %time function(next_prime(2^31))
verbose 0 (3837: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
implementation.  
# 5 more times above message 
CPU times: user 36min 28s, sys: 9.23 s, total: 36min 38s
Wall time: 37min 27s
[1]

I guess that it has something to do with 32-bits computer integers. The point is that my computer is 64-bits.

Question: Is there a way to avoid this slow-down (at least for $p<2^{63}$)?

I made a computation involving the computation of a Groebner basis under a finite field of large characteristic $p$.

If $p<2^{31}$ then everything is ok:

sage: %time function(previous_prime(2^31))
CPU times: user 875 ms, sys: 31 ms, total: 906 ms
Wall time: 1.14 s
[1]

But if $p>2^{31}$ then the computation became very slow:

sage: %time function(next_prime(2^31))
verbose 0 (3837: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.  
# 5 more 6 times above message 
CPU times: user 36min 28s, sys: 9.23 s, total: 36min 38s
Wall time: 37min 27s
[1]

I guess that it has something to do with 32-bits computer integers. The point is that my computer is 64-bits.

Question: Is there a way to avoid this slow-down (at least for $p<2^{63}$)?

I made a computation involving the computation of a Groebner basis under a finite field of large characteristic $p$.

If $p<2^{31}$ then everything is ok:

sage: %time function(previous_prime(2^31))
CPU times: user 875 15 ms, sys: 16 ms, total: 31 ms, total: 906 ms
Wall time: 1.14 s
[1]
28.3 ms
[v0 + 357913941, v1 - 357913941]

But if $p>2^{31}$ then the computation became very slow:

sage: %time function(next_prime(2^31))
verbose 0 (3837: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.  
# 6 times above message 
implementation.
CPU times: user 36min 28s, 125 ms, sys: 9.23 s, 219 ms, total: 36min 38s
344 ms
Wall time: 37min 27s
[1]
3.09 s
[v0 + 357913943, v1 + 1789569716]

I guess that it has something to do with 32-bits computer integers. The point is that my computer is 64-bits.

Question: Is there a way to avoid this slow-down (at least for $p<2^{63}$)?

def function(p):
    F=GF(p)
    R.<v0, v1>=PolynomialRing(F,2)
    Eq=[3*v0 + 5*v1 + 1/F(3), 
    9*v0^2 + 15*v1^2 - 2/F(3), 
    3*v0^3 + 5*v1^3 - v0^2 + 1/F(27)]
    Id=Ideal(Eq)
    G=Id.groebner_basis()
    return G