GP/PARI 中的 setsearch：测试立方留数

Question

我正在尝试在 GP/PARI 中编写一个程序，它给定一个有限域（在本例中，我将使用 p=3 上 9 个元素的 2 度域），计算所有元素的立方并将其存储在列表中（我知道这是非常低效的）。然后，我想在同一域中的点处评估一些函数并测试它是否在这个列表中（是否是立方留数）。我正在尝试使用 GP/PARI 中的列表然后使用 setsearch 来完成此操作。

我首先定义不可约多项式 mod 3。然后，我遍历 9 元素域中的所有元素，将它们求立方并将其存储在列表中，该列表被实现为该多项式环的商（双模）。一旦我有了这个列表，我现在就遇到了 setsearch 的麻烦。首先，列表似乎是以双模形式存储的。视觉上非常丑陋，但我不介意，只要它可以进行计算。然而，似乎不能。例如，0 应该在列表中，但使用 setsearch 测试它会返回 false。我猜原因是在列表中，0存储为

Mod(Mod(0,3),rpoly)

事实上（见下文），情况似乎确实如此。然而，更糟糕的事情正在发生。 >

(15:45) gp > rpoly=Mod(1,3)*(x^2-x-1);
(15:45) gp > polisirreducible(rpoly)
%2 = 1
(15:45) gp > cubic=listcreate(9);
(15:45) gp > for(a=0,2,for(b=0,2,listput(cubic,Mod(Mod(1,3)*(a*x+b)^3,rpoly))))
(15:46) gp > cubic
%5 = List([Mod(Mod(0, 3), Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3)), Mod(Mod(1, 3), Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3)), Mod(Mod(2, 3), Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3)), Mod(Mod(2, 3)*x + Mod(1, 3), Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3)), Mod(Mod(2, 3)*x + Mod(2, 3), Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3)), Mod(Mod(2, 3)*x, Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3)), Mod(Mod(1, 3)*x + Mod(2, 3), Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3)), Mod(Mod(1, 3)*x, Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3)), Mod(Mod(1, 3)*x + Mod(1, 3), Mod(1, 3)*x^2 + Mod(2, 3)*x + Mod(2, 3))])
(15:46) gp > setsearch(cubic,Mod(Mod(0,3),rpoly))
%6 = 0
(15:47) gp > setsearch(cubic,Mod(Mod(0,3)*x+Mod(0,3),rpoly))
%7 = 1

因此，它似乎不仅拒绝承认 0 在列表中，而且甚至在穿过该字段时自然会遇到的其他形式的 0 也不起作用：它特别想要 %7

为什么会发生这种情况？更重要的是，有什么办法可以解决这个问题来实现我的目标吗？

Answer 1

我不知道 gp，但你能验证你的立方列表是否正确吗？我得到以下信息。

((0x + 0)^3) mod (x^2 - 1x - 1) = 0x + 0 = {0,0}
((0x + 1)^3) mod (x^2 - 1x - 1) = 0x + 1 = {0,1}
((0x + 2)^3) mod (x^2 - 1x - 1) = 0x + 2 = {0,2}
((1x + 0)^3) mod (x^2 - 1x - 1) = 2x + 1 = {2,1}
((1x + 1)^3) mod (x^2 - 1x - 1) = 2x + 2 = {2,2}
((1x + 2)^3) mod (x^2 - 1x - 1) = 2x + 0 = {2,0}
((2x + 0)^3) mod (x^2 - 1x - 1) = 1x + 2 = {1,2}
((2x + 1)^3) mod (x^2 - 1x - 1) = 1x + 0 = {1,0}
((2x + 2)^3) mod (x^2 - 1x - 1) = 1x + 1 = {1,1}

所有 8 个非零元素都可以被视为 1x + 0 的幂：

((1x + 0)^0) mod (x^2 - 1x - 1) = 0x + 1 = {0,1}
((1x + 0)^1) mod (x^2 - 1x - 1) = 1x + 0 = {1,0}
((1x + 0)^2) mod (x^2 - 1x - 1) = 1x + 1 = {1,1}
((1x + 0)^3) mod (x^2 - 1x - 1) = 2x + 1 = {2,1}
((1x + 0)^4) mod (x^2 - 1x - 1) = 0x + 2 = {0,2}
((1x + 0)^5) mod (x^2 - 1x - 1) = 2x + 0 = {2,0}
((1x + 0)^6) mod (x^2 - 1x - 1) = 2x + 2 = {2,2}
((1x + 0)^7) mod (x^2 - 1x - 1) = 1x + 2 = {1,2}
((1x + 0)^8) mod (x^2 - 1x - 1) = 0x + 1 = {0,1} (sequence repeats)

因此可以使用对数和反对数的等效项来实现乘法或求幂：

((2x + 2)^3) => ((1x + 0)^6)^3 => ((1x + 0)^(18 mod 8)) => (1x + 0)^2 => 1x + 1