НОД многочленов по модулю k

Я хочу попросить Matlab сообщить мне, например, наибольший общий делитель полиномов x^4+x^3+2x+2 и x^3+x^2+x+1 над такими полями, как Z_3[x] ( где ответ x+1) и Z_5[x] (где ответ x^2-x+2).

Есть идеи, как мне это реализовать?


matlab polynomials algebra finite-field
person Maths student    schedule 16.03.2015    source источник
comment
Вы хотите реализовать алгоритм самостоятельно или можете использовать существующую реализацию, подобную этой? mathworks.com/help/symbolic/mupad_ref/gcd.html   -  person eigenchris    schedule 16.03.2015
comment
@eigenchris говорит, что вы не можете использовать это в Matlab? Я не собираюсь реализовывать свой собственный алгоритм, я просто хочу, чтобы что-то вычислило его для меня. (Я пробовал wolfram alpha, но каждый ответ выходит как 1!)   -  person Maths student    schedule 16.03.2015
comment
(На самом деле ошибка пользователя может быть причиной того, что она выходит как 1, но мне все же нужен способ вычислить это с помощью Matlab)   -  person Maths student    schedule 16.03.2015
comment
Это не должно быть так сложно: en.wikipedia.org/wiki/   -  person knedlsepp    schedule 16.03.2015

Ответы (1)


arrow_upward
2
arrow_downward

Вот простая реализация. Полиномы кодируются как массивы коэффициентов, начиная с самой низкой степени: так, x^4+x^3+2x+2 равно [2 2 0 1 1]. Функция принимает два полинома p, q и модуль k (который должен быть простым, чтобы алгоритм работал).

Примеры:

  • gcdpolyff([2 2 0 1 1], [1 1 1 1], 3) возвращает [1 1], что означает 1+x.
  • gcdpolyff([2 2 0 1 1], [1 1 1 1], 5) возвращает [1 3 2], что означает 1+3x+2x^2; это не согласуется с вашим ответом, но я проверил вручную, и кажется, что ваш ответ неверен.

Функция сначала заполняет массивы, чтобы они были одинаковой длины. Пока они не равны, он идентифицирует полином более высокой степени и вычитает из него полином более низкой степени, умноженный на соответствующую степень x. Это все.

function g = gcdpolyff(p, q, k)
p = [p, zeros(1, numel(q)-numel(p))];
q = [q, zeros(1, numel(p)-numel(q))];
while nnz(mod(p-q,k))>0
    dp = find(p,1,'last');
    dq = find(q,1,'last');
    if (dp>=dq)
        p(dp-dq+1:dp) = mod(p(1+dp-dq:dp) - q(1:dq), k);
    else
        q(dq-dp+1:dq) = mod(q(dq-dp+1:dq) - p(1:dp), k);
    end
end
g = p(1:find(p,1,'last'));
end

Имена переменных dp и dq немного вводят в заблуждение: это не степени p и q, а скорее степени + 1.

person Community    schedule 17.03.2015