Re: Looking for algorithm

From: Vedat Hallac (vman_at_black.hole.com)
Date: 02/18/05 

Date: Fri, 18 Feb 2005 19:52:33 +1000

On Fri, 18 Feb 2005 06:25:47 +0000, David Wagner wrote:

> Here is the general form of my solution, I think. It might help see
> how to move it from the integers to GF(2), and elsewhere.
>
> Pick a finite field F. (Maybe a ring will suffice?) Express the data
> as a sequence of values from F, which are treated as the coefficients of
> a polynomial D(X) in F[X]. Pick a polynomial P(X) that divides X^n -
> 1 in F[X]. Form the ring R = F[X]/(P(X)). Choose a value \alpha that
> is a root of P(X) in some extension field FF. Define the polynomial
> evaluation function eval_\alpha : f(X) |--> f(\alpha). Make sure
> you chose \alpha so that eval_\alpha(P(X)) = 0, so that we can view
> eval_\alpha as a map with signature R -> FF. Fix a value \beta in FF.
> A checksum is a polynomial C(X) in R of degree less than k, where
> k is some parameter. Given data value D(X), we compute C(X) as the
> polynomial satisfying eval_\alpha(D(X)*X^k + C(X)) = \beta and deg C(X)
> < k. (You could choose a sequence of \alpha's and \beta's and get a
> sequence of C(X)'s as your checksum.)
>
> My 40||8 solution involved taking n = 48, FF = F = Z/97Z, P(X) = X^48 - 1,
> \alpha = 2, \beta = 1, k = 1, so that the checksum was a value in Z/97Z.
>
> We could also try working over GF(2) as follows: take n = 48, F = GF(2),
> P(X) = some divisor of X^48 + 1 in GF(2)[X], \alpha = X, k = deg P(X),
> FF = GF(2^k), \beta = 1. However, I can't seem to find a suitable value
> for P(X) that yields an efficient scheme.
>
> We could also imagine trying other variations: say, GF(3) and k = 5.
> I haven't checked to see whether this leads to any other good schemes.
> There are many options.

My pitiful finite field knowledge is being sorely tested, I am afraid.
I've used PARI/GP to test a few polynomials, to see how well I understood
the construction. And I learned that I either missed something, or there
is something wrong here. Let me run through my small experiment, and tell
about the results. I've started with factoring 2^48+1 in GF(2):

factor(Mod(1,2)*(x^48+1))

[Mod(1, 2)*x + Mod(1, 2) 16]

[Mod(1, 2)*x^2 + Mod(1, 2)*x + Mod(1, 2) 16]

Meaning (no offense intended if you do know PARI/GP speak :-) ) 16 roots
at x+1 and 16 more at x^2+x+1. BTW, I am dropping the Mod(1,2) for
clarity. This sort of limits the P(X) we can choose. My first trial was
the obvious:

p=(Mod(1,2)*(x+1))^8 = x^8+1

Then I defined my data vector:

d=vector(40)
d[39]=d[37]=d[23]=d[17]=d[9]=d[3]=d[1]=1
d=Mod(1,2)*d

>From now on, things get shaky, because I don't exactly know the
definitions of some terms. I *really* need to go back and read up
again. For example for ring operations I use "modulo the polynomial
P(x)". The eval_\alpha function barely registers its existence in my
brain, but I think your choices would simply equate to "the resulting
polynomial in FF with same coefficients". So, I only work in R for the
time being (as FF=GF(2^8) wouldn't need to modify the remainder from
dividing by P(x)). Since beta=1, c(x) is 1+d(x)*x^8, or

c=((Pol(d)*x^8)+Mod(1,2))%p

in PARI/GP. Which results in c(x)=x^7+x^5+x^3+1. From d and c, I create my
combined data vector, dd:

dd=concat(d,Vec(c))

Double check:

Pol(dd)%p => 1

Yippe. Let's define some handy functions:

rol(v)=concat(vecextract(v,concat("2..",length(v))),v[1])

rot(v,n)=for(i=1,n,v=rol(v));v

Now, let's test it:

for(i=1,48,print(Pol(rot(dd,i))%p))
Mod(1, 2)*x
Mod(1, 2)*x^2
Mod(1, 2)*x^3
Mod(1, 2)*x^4
Mod(1, 2)*x^5
Mod(1, 2)*x^6
Mod(1, 2)*x^7
Mod(1, 2)
Mod(1, 2)*x
Mod(1, 2)*x^2
Mod(1, 2)*x^3
Mod(1, 2)*x^4
Mod(1, 2)*x^5
Mod(1, 2)*x^6
Mod(1, 2)*x^7
... repeat ...

Clearly there is a problem. Where do you think I've gone wrong? Should I
not reduce the polynomials in ring R before moving them to GF(2^k)?
Clearly P(x) is not a very good field polynomial for GF(2^k) :-) That is
why I left everything in R, but the reality decided to catch up with me.

Or should I choose a P(x) which is irreducible? If that is the case, then
how do you think we can work with 48 bits? Multiple \beta values with each
irreducible P(x)? we can have two betas for p(x)=x+1, and 3 for
p(x)=x^2+x+1, which adds up to 13 bits of checksum. But I don't know how
we can construct the full checksum with these. Let me play with it a bit
more. I'll post if I can come up with something worth mentioning.

Or maybe first I should learn to walk before I try to run?

Cheers,
vedaT

Relevant Pages

  • Re: Possible flaw in the polynomial ring A[X] construction
    ... distinguish it from the product of polynomial functions. ... for rings of finite characteristic, so let us consider the base ring to ... the ring of polynomials over this field is ... with the base ring being the field of two elements. ...
    (sci.math)
  • Re: Possible flaw in the polynomial ring A[X] construction
    ... with further operations such as a quotient ring. ... then the ring Aof polynomials with real coefficients, ... than just heaping piles of construction upon other piles of ... "While the polynomial itself is necessarily infinite in length, ...
    (sci.math)
  • Re: Understanding the quotient ring nomenclature
    ... A ring is defined as containing elements. ... undefined domain and an infinite length of terms. ... infinite series are reals. ... long as the two polynomials being multiplied have finitely many terms, ...
    (sci.math)
  • Re: Confirmed flaw in the polynomial ring A[X] construction
    ... different ring*. ... all the polynomials would get ... does not address the polynomial with real coefficients and the effect ... usage or construction composed with y. ...
    (sci.math)
  • Re: Possible flaw in the polynomial ring A[X] construction
    ... Because in an arbitrary ring, with elements a_i, the sum ... And in the reals it is also not defined only by the addition ... of the formalisms can be recovered from the ring definition. ... The ring of polynomials is a subring of that ring. ...
    (sci.math)