How do you find GCD of polynoms?

[Antrax]

Has to do with finding square roots modulo N=4k+1. The algorithm we were presented with relied on the ability to find a polynomial GCD of two polynoms, modulo something. How does that work, precisely? I tried using Euclid's algorithm, but you get residues that are of a higher degree than that of the number you're dividing, which hints the algorithm won't necessarily ever stop, etc. How are you supposed to do it?
Antrax

------------------
"Look, that's why there's rules, understand? So that you think before you break 'em" - Lu-Tze, Thief of Time

[zeek]

[Antrax]

I'll give you the example:

find the GCD of X^6-1 and X^2-x+7 (mod 13).
So we'll get:
x^6-1 = x^4(x^2-x+7)+x^5-7x^4-1
and now we'll have to divide x^2-x+7 with x^5-7x^4-1, which leads to negative degrees, which contradicts the proof that the algorithms stops after log(a) of steps, etc.
Antrax

------------------
"Look, that's why there's rules, understand? So that you think before you break 'em" - Lu-Tze, Thief of Time

[zeek]

Like I said, you're not finished dividing.
(x^2-x+7) can still divide into (x^5-7x^4-1).

[zeek]

If I didn't screw this up...

x^6 - 1 = (x^2-x+7)(x^4+x^3-6x^2-13x+29) + (120x-204)

[Antrax]

How do you find the GCD from that?
Antrax

------------------
"Look, that's why there's rules, understand? So that you think before you break 'em" - Lu-Tze, Thief of Time

[zeek]

Well if my math was right, you then have to divide (120x-204) into (x^2-x+7). Since (120x-204) = 12(10x-17), it's easy to see they have no common factor, so the GCD is 1.

[Antrax]

But but, the GCD is (x-3).
x^2-x+7 = (x-3)(x+2) (mod 13)
x^6 - 1 = (x-3)(x^2+6x+9)(x^3+1) (mod 13)
Antrax


------------------
"Look, that's why there's rules, understand? So that you think before you break 'em" - Lu-Tze, Thief of Time

[zeek]

Oh, I see where you going with this. mod 13.
How about this:
120x-204 = 120(x-3) + 12*13, so

120x-204 = (x-3)120 (mod 13)
x^2-x+7 = (x-3)(x+2) (mod 13)

[zeek]

Here's an approach.
Since 120 and x aren't divisible by 13, you can do..

120(x^2-x+7) - x(120x-204) = 84x + 840 = 84(x+10)
and
(x+10) = (x-3) (mod 13)

[kevinatilusa]

If you were working in the real numbers and you had ax^2+bx+c and dx+e, you would take as your next step (ax^2+bx+c)-(a/d)(x)(dx+e) to eliminate the quadratic term. When we're working mod 13, we can do a similar thing, but just take a*d^(-1) instead of a/d (where d^(-1) is such that d*(d^(-1))=1 (mod 13), which you can find by the old-fashioned Euclidean algorithm).

[lurker]

Why work with big numbers? Being in 'mod 13' already... 120x-204 is simply 3x+4, and so x²-x+7=(3x+4)*(9x+5) [having the table of multiplication in Z₁₃ surely helps!]. Of course, myGCD = 3x+4 = 3x+4+13+13 = 3x+30 = 3(x+10) ~ x+10 = x+10-13 = x-3 = yourGCD...