# Unbalanced Feistel network only generates complete permutations with square lengths

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)?

• if d = sqrt(period), then period = d*d, and the line s = d + period - d*d becomes s = d + period - period which is simply equal to d? Is that supposed to be that way? Jun 24, 2018 at 0:35
• That's almost correct, d is an unsigned number however so it's effectively floor(sqrt(period)). s is whats leftover. e.g, for period = 113, d = 10 and s = 13. Jun 24, 2018 at 2:36
• @EllaRose I am such a moron, I can't believe I "corrected" you -- you are absolutely right, that was a typo on my behalf. Jun 25, 2018 at 18:40

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$.
• The reason you get a maximal permutation when period is a complete square is because then $s=d$. Jun 24, 2018 at 22:20