view release on metacpan or  search on metacpan

docs/index.md  view on Meta::CPAN

      A        B        C        D
    (0, 0)   (0, 1)   (1, 0)   (1, 1)

It's easy to see that \\(A\\) is the neutral element with respect to the
sum, and that the following summing table applies taking into
consideration the sum of respective coordinates modulo 2:

    + A B C D
     +-------
    A|A B C D
    B|B A D C
    C|C D A B
    D|D C B A

This is actually the same table we would find considering the polynomials
associated to each element, namely:

\\[A \rightarrow 0 \\\
B \rightarrow 1 \\\
C \rightarrow x \\\
D \rightarrow x + 1 \\\]

Now we need to compute the product table, and for this we need an
irreducible polynomial of degree 2 over \\(Z_2\\). It turns out that this
polynomial is one and only one: \\(x^2 + x + 1\\). Let's see what happens
by first computing the products

\\[A \cdot X = X \cdot A \rightarrow (0) \cdot X = X \cdot (0) = (0) \\\
B \cdot X = X \cdot B \rightarrow (1) \cdot X = X \cdot (1) = X \\\
C \cdot C \rightarrow (x) \cdot (x) = x^2 \\\
C \cdot D = D \cdot C \rightarrow (x) \cdot (x + 1) = (x + 1) \cdot (x) = x^2 + x \\\
D \cdot D \rightarrow (x + 1) \cdot (x + 1) = x^2 + 1 \\]

where uppercase \\(X\\) is any of \\({A, B, C, D}\\).

Now we must compute the rests modulo the irreducible polynomial:

\\[(0) \mod (x^2 + x + 1) = (0) \rightarrow A \\\
(X) \mod (x^2 + x + 1) = (X) \rightarrow X \\\
(x^2) \mod (x^2 + x + 1) = (x + 1) \rightarrow D \\\
(x^2 + x) \mod (x^2 + x + 1) = (1) \rightarrow B \\\
(x^2 + 1) \mod (x^2 + x + 1) = (x) \rightarrow C \\]

So, we have our multiplicative table at last:

    * A B C D
     +-------
    A|A A A A
    B|A B C D
    C|A C D B
    D|A D B C

It's easy to see that this is indeed a *good* multiplicative table for a field.

## Irreducible Polynomial of Order \\(n\\)?

Now that we have a trick, we still have to find out one last way to
actually find an irreducible polynomial of the desired order \\(n\\) over
the field we are extending. There are some results about it:

- they actually exist! There is someone that calculated a formula to count
  them, which also implies that fields of order \\(p^n\\) exists, of
  course! See [this question][irred-count] for further information;
- there always exist *monic* ones, i.e. where the coefficient for the
  highest power of \\(x\\) is \\(1\\) (which simplifies the division and
  the rest calculation);
- there's more than one way to test for the irreducibility of
  a polynomial... but we only need one, of course.

For the second bullet, we will refer to [Rabin's test for
irreducibility][rabin-test] with the algorithm that follows (in Perl)
built using `Math::GF` (and in particular using elements in
`Math::GF::Zp`) and [Math::Polynomial][]:

    # Input $f is a Math::Polynomial object built over Zp
    sub rabin_irreducibility_test {
       my $f    = shift;
       my $n    = $f->degree;
       my $one  = $f->coeff_one;
       my $pone = Math::Polynomial->monomial(0, $one);
       my $x    = Math::Polynomial->monomial(1, $one);
       my $q    = $one->n;
       my $ps   = prime_divisors_of($n);
    
       for my $pi (@$ps) {
          my $ni  = $n / $pi;
          my $qni = $q**$ni;
          my $h = (Math::Polynomial->monomial($qni, $one) - $x) % $f;
          my $g = $h->gcd($f, 'mod');
          return if $g->degree > 1;
       } ## end for my $pi (@$ps)

       my $t = (Math::Polynomial->monomial($q**$n, $one) - $x) % $f;
       return $t->degree == -1;
    } ## end sub rabin_irreducibility_test

The call to `prime_divisors_of($n)` returns all distinct prime divisors of
`$n`.

The test above is slightly different from the one described in the
Wikipedia page, but not that much.

So... to find an irreducible polynomial of a pre-defined degree \\(n\\)
over a pre-defined field \\(Z_p\\), we can just start enumerating all
*monic* polynomials from \\(x^n + 1\\) on and apply the test... we will
eventually hit one!


# Projective Plane

The definition of [projective plane][] is the following:

> A projective plane consists of a set of lines, a set of points, and
> a relation between points and lines called incidence, having the
> following properties:
>
> - Given any two distinct points, there is exactly one line incident with
> both of them.
>
> - Given any two distinct lines, there is exactly one point incident with
> both of them.