Efficient calculation of difference sets from finite fields

Question

A while ago I wrote a program to generate, amongst other things, difference sets from finite fields. Generating these sets is rather slow. Is there some theorem or construction I could use to speed it up?

I basically use the method shown in Singer(1938). Starting with an $a$ dimensional monic primitive polynomial $g_d$ over $\mathbb{F}_{p^b} = \mathbb{F}_p(k)$. If $v$ is a root of $g_d$ then non-zero elements of $\mathbb{F}_p(v)$ can be expressed as a power of $v$ or as a max degree $a-1$ polynomial over $v$ with coefficients $c_n \in \mathbb{F}_p(k)$.

$$v^n=\sum_{i = 0}^{a-1} c_i\:v^i$$

To find the difference set, I iteratively raised the power of $v$ up to $v^{\frac{p^{ab}-1}{p^b-1}-1}$, recording which powers of $v$ produced polynomials where $c_{a-1} = 0$.

Of course, I also have to get $g_d$, but even when I find all valid and distinct $g_d$ polynomials, calculating the difference sets is by far the slowest part. For $p = 5, a = 3, b = 2$, finding the difference sets slows the program down by an order of magnitude.

An observation I did make is that it is the parent degree $ab$ polynomial over $\mathbb{F}_p$, $f_m$, not $g_d$, that determines what specific difference set we get, since $0$ is a fixed point of $r \mapsto r^p$. I thought about directly starting from the vector space representation, but that involves finding the discrete log of complicated polynomials over $k$ and $v$ versus simple shift and carry operations.

Answer 1

Assume you have the following things:

• Log tables for $u$, an arbitrary primitive element of $\Bbb{F}_p(v)$
• The log $u$ values of $k$ and $v$

You are likely to have these on hand from when you generated $g_d$ in the first place. Then we can generate the desired logs base $v$ easily.

We want to generate the logs of all non-zero $k$-$v$ polynomials with $v$-degree less than $a-1$ up to multiplication by $r \in \Bbb{F}_p(k)^{\times}$. If we were fully efficient in iteration we'd only have to iterate over $\frac{p^{(a-1)b}-1}{p^b-1}$ polynomials, a saving of nearly $p^b$-fold iterations. Here's how you can efficiently iterate over the desired polynomials

#pre-defined functions/lists/etc. needed
logu(x): finds logs base u
alogu(y): finds antlogs base u
modinv(z, period): finds the modular inverse.

#constants
p, a, b: given parameters
per, kper: (p^(ab) - 1) and (p^b - 1) respectively
beat = per/kper 

d = logu(v)
lk = logu(k)
dinv = modinv(d, per)

let plog_list be an empty list

for i from 0 to a-2:
    let temp_list be an empty list

    for all plog in plog_list:
        for cof from 0 to kper-1:
            ucof = cof*lk
            term = ucof + d*i
            np = (alogu(term mod per) + alogu(plog)) mod p
            nplog = logu(np)
            add nplog to temp_list

    put d*i into temp_list
    put all elements of temp_list into plog_list

let diff_set = {(x*dinv) mod beat | x in plog_list}

The basic idea for this iteration is as follows:

The $i$th step starts with all non-zero polynomials with $v$-degree at most $i-1$ whose lowest non-zero term has coefficient $1$. For each polynomial $t$ we start with and for each coefficient $r \in \Bbb{F}_p(k)^{\times}$, we put $rv^i + t$ in our working set. After all of this, we add $v^i$ to out working set, then merge our working and starting sets together and pass it to the $i+1$th step.

The other advantage here is that you're nearly always working with integers, while the shift-and-carry method almost certainly uses bulkier data types more often.