Unbalanced Feistel network only generates complete permutations with square lengths

Question

I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then cycle after having reached each of them all exactly once.

Rather than splitting the counter into two equally sized bitvectors $L$ and $R$, I'm operating on a quotient and remainder, with the ambition of generating permutations of arbitrary length, unlike the $2^n$ that a balanced network or maximal LSFR might generate.

uint16_t feistel(uint16_t counter, unsigned period)
{
    uint16_t d = sqrt(period);
    uint16_t s = period - d*d;
    uint16_t q = counter / d;
    uint16_t r = counter % s;

    for (int i = 0; i < 3; i++)
    {
        uint16_t nr = r;
        uint16_t F = (i * r + q);
        r =  F % d;
        q = nr;
    }

    return q*d + r;
}

This code can correctly generate some maximal permutations. However, it only does so for periods that are square numbers (where s = 0).

Can this be changed so that any choice of period generates a complete permutation? Also, are there any broader numerical issues surrounding the choice of how a number is split and manipulated in an unbalanced Feistal network (divisor * quotient + remainder, sum of two primes, left and right bitvectors, etc)?

Answer 1

I think that this method of yours will not work out. The reason is the way you compute $r = counter$ mod $s$.
Take a simple example of $(counter_1, period) = (3, 11)$ and $(counter_2, period) = (5, 11)$. Here $d=3$ and $s=5$.
You get initial $(q_1, r_1) = (1,3)$ and $(q_2, r_2) = (1,0)$.
After first iteration of the loop, you have $(q_1, r_1) = (3,1)$ and $(q_2, r_2) = (0,1)$.
After the second interation of the loop, you will get $(q_1, r_1) = (1,1)$ and $(q_2, r_2) = (1,1)$.
Now, for the remaining iterations, both $(q_1,r_1)$ and $(q_2,r_2)$ will always go along being equal and will finally result in equal values being returned by the function for 2 different counter values with the same period sabotaging the maximal permutation.
You should get rid of the above mentioned issue by computing initial $r$ as $r = counter$ mod $d$.