sage - SageMath：确定字段中可约多项式数量的最佳方法？

Question

假设我有多项式f(x) = x^n + x + a。n我为和希望设置了一个值，我设置的其他值0 <= a <= A在哪里。A这意味着我将有总共A不同的多项式，因为a可以是 和 之间的任何0值A。

使用 Sage，我想找到这些可约A多项式的数量。例如，假设我设置n=2和A=10^6。我希望能够确定这些10^6多项式中有多少是可约的。我可以帮助构建一个 Sage 流程来执行此操作吗？注意： Sage 有is_irreducible()方法，但我不知道如何在这里应用它，因为我有很多多项式可以调用该方法。

我最初只是考虑循环A时间和增加计数，但我觉得必须有一种更有效的方法来做到这一点？如果我这样做，那么我需要的 A 的大值（如 10^6）将需要很长时间。

标签： sage

Answer 1

一种天真的方法：

sage: F = GF(next_prime(10^6))
sage: R.<x> = F[] # replace F with your favorite field
sage: def count(A):
....:     c = 0
....:     for a in range(A):
....:         if not (x^2+x+a).is_irreducible():
....:             c += 1
....:     return c
....: 
sage: count(10^4)
5031
sage: count(10^5)
50066
sage: %time count(10^6)
CPU times: user 13.2 s, sys: 5.15 ms, total: 13.2 s
Wall time: 13.2 s
500000

速度可能会因领域而异。

您还可以向count— def count(A, n=2):— 添加一个可选参数，然后将多项式更改为x^n+x+a。usingn=8比 using 慢 2 或 3 倍n=2。