setsearch в GP/PARI: тестирование кубических остатков

Question

Я пытаюсь написать программу в GP/PARI с заданным конечным полем (в этом примере я буду использовать поле степени 2 из 9 элементов по p=3), вычислить куб всех элементов и сохранить его в списке (Я так понимаю это очень неэффективно). Затем я хочу оценить некоторые функции в точках одного и того же поля и проверить, находится ли он в этом списке (является ли он кубическим остатком). Я пытаюсь сделать это с помощью списков в GP/PARI, а затем с помощью setsearch на нем.

Сначала я определяю свой неприводимый полиномиальный мод 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)

Таким образом, умножение или возведение в степень может быть реализовано с использованием эквивалента log и antilog:

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