[snip]
The problem now is that division cannot always be computed in the first
instance [as I understand it, and well as I understand math isn't saying
much]. Say you have

p(x) = 3x^2 + 4x + 1
and
q(x) = 7x + 9

If you attempt to divide p(x)/v(x) over Z^k[x] there is no solution since
you have to multiply q(x) by (3/7)x and subtract that out to clear the x^2
term. Since 3/7 == 0 over Z you cannot complete this operation for all
polynomials.
[snip]

In this case you can't express p(x) as a(x)*q(x)+r(x)
with a(x) and r(x) having integer coefficients. But
what is the practical 'consequence' of that for you?
(What are the applications demanding such expressions?)

Mok-Kong Shen a écrit :
In this case you can't express p(x) as a(x)*q(x)+r(x)
with a(x) and r(x) having integer coefficients. But
what is the practical 'consequence' of that for you?
(What are the applications demanding such expressions?)

Exact. That's why we used the so-called pseudo-division:
kP = AQ + R.
A practical use? Computation of GCDs, for instance.

This is somewhat basic and is explained in most books. Notably
in Knuth

"Marcel Martin" <mm@ellipsa.no.sp.am.net> wrote:

Mok-Kong Shen a écrit :
In this case you can't express p(x) as a(x)*q(x)+r(x)
with a(x) and r(x) having integer coefficients. But
what is the practical 'consequence' of that for you?
(What are the applications demanding such expressions?)

Exact. That's why we used the so-called pseudo-division:
kP = AQ + R.
A practical use? Computation of GCDs, for instance.

This is somewhat basic and is explained in most books. Notably
in Knuth :-)

Um maybe I misunderstand this but if you multiply P by k don't you have to
muliply the right side to maintain the equality? Essentially I'd have to
multiply the leading digit of P to form the least common multiple between
the digit of P and A. But I'd have to repeat this for every digit of the
quotient. Is that mathematically valid? The pseudo code would be like
[snip]

Tom St Denis wrote:

"Marcel Martin" <mm@ellipsa.no.sp.am.net> wrote:

Mok-Kong Shen a écrit :
In this case you can't express p(x) as a(x)*q(x)+r(x)
with a(x) and r(x) having integer coefficients. But
what is the practical 'consequence' of that for you?
(What are the applications demanding such expressions?)

Exact. That's why we used the so-called pseudo-division:
kP = AQ + R.
A practical use? Computation of GCDs, for instance.

This is somewhat basic and is explained in most books. Notably
in Knuth :-)

Um maybe I misunderstand this but if you multiply P by k don't you have to
muliply the right side to maintain the equality? Essentially I'd have to
multiply the leading digit of P to form the least common multiple between
the digit of P and A. But I'd have to repeat this for every digit of the
quotient. Is that mathematically valid? The pseudo code would be like
[snip]

Maybe I misunderstood you, but you multiply the 'whole'
of P(x) (not just any part of P(x)) with an integer and
treat it as if this was given instead of the original
P(x), so that the division is now possible.

In article <zM8Ib.2272$INs.322@twister01.bloor.is.net.cable.rogers.com>,
Tom St Denis <tomstdenis@iahu.ca> wrote:
At the end of the algorithm I've multiplied P by G to form the quotient.
Does this mean that the quotient is G times too big? Let's try this with

p(x) = 3x^2 + 4x + 1
and
q(x) = 7x + 9

So the LCM of 3,7 is 21 so multiply p by 7 to get

21x^2 + 28x + 7

now subtract 3x*q(x) to get p(x) - 3x*q(x) = 1x + 7, G = 7

now LCM of 1,7 is 7 again, so multiply p(x) by 7 to get

I think that here, you're overlooking the original
p(x)... which also has to be multiplied by 7
(again).

p(x) = 7x + 49

now subtract q(x) to get p(x) - q(x) = 42, G = 49

That should be 40, not 42; after all, it isn't the
answer to life, the universe, and everything.

Now I'm a bit lost... seems the quotient is what, 3x + 1 and the
remainder
is 42. But clearly (7x + 9)(3x + 1) = 21x^2 + 34x + 9 + 42 = 21x^2 + 34x
+
51 is not equal to the original dividend.

The equation should now be:
49*p(x) = (21x + 1)q(x) + 40

147x^2 + 196x + 49 = (21x + 1)(7x + 9) + 40
147x^2 + 7x + 189x + 9 + 40
147x^2 + 196x + 49

N'est-ce pas?

"Gregory G Rose" <ggr@qualcomm.com> wrote in message
news:bssa7b$37d@qualcomm.com...
In article <zM8Ib.2272$INs.322@twister01.bloor.is.net.cable.rogers.com>,
Tom St Denis <tomstdenis@iahu.ca> wrote:
At the end of the algorithm I've multiplied P by G to form the quotient.
Does this mean that the quotient is G times too big? Let's try this with

p(x) = 3x^2 + 4x + 1
and
q(x) = 7x + 9

So the LCM of 3,7 is 21 so multiply p by 7 to get

21x^2 + 28x + 7

now subtract 3x*q(x) to get p(x) - 3x*q(x) = 1x + 7, G = 7

now LCM of 1,7 is 7 again, so multiply p(x) by 7 to get

I think that here, you're overlooking the original
p(x)... which also has to be multiplied by 7
(again).

But p(x) = 1x + 7 is the remainder of 7*p(x) - 3x*q(x) [for the original
p(x)]

p(x) = 7x + 49

now subtract q(x) to get p(x) - q(x) = 42, G = 49

That should be 40, not 42; after all, it isn't the
answer to life, the universe, and everything.

Hehehe, oops yeah.

Now I'm a bit lost... seems the quotient is what, 3x + 1 and the
remainder
is 42. But clearly (7x + 9)(3x + 1) = 21x^2 + 34x + 9 + 42 = 21x^2 + 34x
+
51 is not equal to the original dividend.

The equation should now be:
49*p(x) = (21x + 1)q(x) + 40

Where did 21x + 1 come from? Does 21x from the fact that you multiply p(x)
by 7 and the quotient coefficient is 3, 3*7=21? But you multiply the p(x)
by 7 to get the last digit too, so why isn't it 21x + 7 ?

147x^2 + 196x + 49 = (21x + 1)(7x + 9) + 40
147x^2 + 7x + 189x + 9 + 40
147x^2 + 196x + 49

N'est-ce pas?

Whoosh.... I'll sort it out eventually.

Thanks!

Tom

In article <zM8Ib.2272$INs.322@twister01.bloor.is.net.cable.rogers.com>,
Tom St Denis <tomstdenis@iahu.ca> wrote:
At the end of the algorithm I've multiplied P by G to form the quotient.
Does this mean that the quotient is G times too big? Let's try this with

p(x) = 3x^2 + 4x + 1
and
q(x) = 7x + 9

So the LCM of 3,7 is 21 so multiply p by 7 to get

21x^2 + 28x + 7

now subtract 3x*q(x) to get p(x) - 3x*q(x) = 1x + 7, G = 7

now LCM of 1,7 is 7 again, so multiply p(x) by 7 to get

I think that here, you're overlooking the original
p(x)... which also has to be multiplied by 7
(again).

p(x) = 7x + 49

now subtract q(x) to get p(x) - q(x) = 42, G = 49

That should be 40, not 42; after all, it isn't the
answer to life, the universe, and everything.

Now I'm a bit lost... seems the quotient is what, 3x + 1 and the remainder
is 42. But clearly (7x + 9)(3x + 1) = 21x^2 + 34x + 9 + 42 = 21x^2 + 34x +
51 is not equal to the original dividend.

The equation should now be:
49*p(x) = (21x + 1)q(x) + 40
147x^2 + 196x + 49 = (21x + 1)(7x + 9) + 40
147x^2 + 7x + 189x + 9 + 40
147x^2 + 196x + 49

N'est-ce pas?

Tout à fait :-)

When multiplying the intermediate remainders, one must also multiply
the intermediate quotients (assuming the final quotient is wanted).

When multiplying the intermediate remainders, one must also multiply
the intermediate quotients (assuming the final quotient is wanted).

[snip]
If we used the trivial algorithm, e.g.

A = 3x^2 + 4x + 1
B = 7x + 9

while (B > 0) {
r = A mod B
A = B
B = r
}

we get

1. r = A mod B = 40, A = B, A = 7x + 9, B = r, B = 40
[snip]

At the end of the algorithm I've multiplied P by G to form the quotient.
Does this mean that the quotient is G times too big?

---- also ---

So far I've implemented quite a few of the basics [division for char!=0 case
only] but I'm stuck on some issues. Everything seems to work well except
for gcd and invmod. First, when computing the gcd I use the characteristic
of the destination polynomial [just easier that way]. The trouble though is
that for any g(x) in GF(p^k)[x] there are at least p GCDs since any h(x) = k
where 1 <= k < p will "divide" g(x) and produce a zero remainder.

In all cases my gcd produces results which even divide the inputs. The
question though is, is it meaningful? How do I handle the trivial cases?
Do I just merge them all into one case? I'd say the operation should be
meaninful since it's part of the definition of irreducible.

However, when I try polynomials which are irreducible such as

x^2 + 4

against say

x + 1

I get a GCD of 5 where I should expect 1 (since x^2 + 4 is irreducible over
GF(17)[x] the poly x+1 cannot divide it).