Re: Looking for algorithm

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 02/21/05 

Date: Mon, 21 Feb 2005 07:39:34 +0000 (UTC)

By the way, here might be another way to think about it. If P(X) divides
X^k - 1, then the order of X modulo P(X) must divide k, and in particular
its order can be at most k. The converse is true, too; if the order of X
modulo P(X) is k, then P(X) divides X^k - 1 but not X^m - 1 for any smaller
m.

Thus we are looking for a polynomial P(X) that divides X^48 - 1 but that
don't divide X^m - 1 for any m<48. This can be rephrased as looking for
P(X) that divides X^48 - 1 but not X^16 - 1 nor X^24 - 1 (since X^i - 1
divides X^j - 1 iff i divides j). And this can be generalized to all n.
I don't have a proof that this is a necessary condition, but it does seem
to be a sufficient condition.

Moreover, it should not be hard algorithmically to determine for which
values of n this leads to a good GF(2)-based checksum. The following
should output for each n the size of the smallest GF(2)-based checksum
it was able to find, and an example of such a polynomial.

FindChecksums():
1. Let n := 1, Z(X) := 1.
2. Let P_n(X) := FindSmallest(X^n - 1, Z(X)).
3. Print (n, deg P_n, P_n(X)).
4. Set Z(X) := lcm(Z(X), X^n - 1), n := n+1, and go back to step 2.

// Returns a polynomial p(x) of minimal degree such that
// p(X) divides Y(X) but does not divide Z(X).
FindSmallest(Y(X), Z(X)):
1. Factor Y(X) as q_1(X)^{e_1} * ... * q_k(X)^{e_k},
   where the q_i(X)'s are all irreducible (over GF(2)) and
   sorted in order of increasing degree.
2. Factor Z(X) as q_1(X)^{f_1} * ... * q_k(X)^{f_k} * z'(X),
   where z'(X) is relatively prime to Y(X).
3. Let p(x) := 1, firsttime := true.
4. For i:=1,..,k, do:
5. If f_i < e_i, then
6. Set p(X) := p(X) * q_i(X)^{f_i}.
7. If firsttime=true, then set p(X) := p(X) * q_i(X), firsttime := false.
8. Return p(x).

If we store all polynomials in factored form, then all of the above steps
are easy (except step 1 of FindSmallest(), but polynomial factoring can be
done in polynomial time, so it shouldn't be too terrible). Thus, I would
expect such an algorithm to be fairly efficient.

Relevant Pages

  • Re: JSH: Polynomial multiples
    ... divides Pin this case in the ring of polynomials, ... algebraic integers, just the integers), yet how it divides the factors x ...
    (sci.math)
  • Re: root of polynomial over galois field
    ... Here we've written "a" in the form of a squarefree factorization, ... Here we reach the Line 14, but now we see c = product, p divides ... not always exist for any element in a Galois field (that is true isnt ... of these polynomials could not be defined either as using the Euclidean ...
    (sci.math.symbolic)
  • Re: multiple.....
    ... ad is multiple of u. ... So any u in Z that divides rsmust divide rs. ... and if f,g are monic polynomials in Ksuch that fg is in Dthen ... Contents of polynomials and invertibility, ...
    (sci.math)
  • Re: Polynomials over Z.
    ... values of a for which Pdivides Q, by lowering the ... the property that there are integer-coefficient polynomials ...
    (sci.math)
  • Re: Divisibility problem
    ... Xan wrote: ... Gerry Myerson ... pdivides qfor all s and all n. ... But what about p and q not constants and coprime polynomials? ...
    (sci.math)
Quantcast