GP/PARI中的setsearch:测试立方残差

Question

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

我首先定义我的不可约多项式mod 3。然后，我遍历我的9元素字段中的所有元素，对它们进行立方运算，并将其存储在一个列表中，该列表被实现为这个多项式环的商(双mods)。一旦我有了这个列表，我现在就遇到了setsearch的麻烦。首先，列表似乎是以双mod的形式存储的。视觉上很难看，但我不介意，只要它能做计算。然而，它似乎不能。例如，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)

因此，乘法或幂运算可以使用log和antilog的等价物来实现：

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