I am looking for algorithms to construct Perfect Difference Sets.
Perfect Difference Sets (PDS) of order $m+1$ are a set of residues $\{d_1, d_2, \cdots, d_{m+1}\} \pmod {q}$ such that every non-zero residue modulo $q$ can be uniquely represented by $d_i - d_j \pmod{q}$ where $d_i, d_j$ are members of the PDS. Singer [Singer1938] gave the criteria that it is necessary that $q = m^2 + m + 1$ and sufficient that $m = p^g$, a prime power in order for a PDS to exist.
Given $q$ that satisfies this criteria, we would like to construct a PDS.
- Any references to algorithms to build the PDS is appreciated.
- If $q$ is prime (or a prime of special form), are there efficient constructions?
References:
[Singer1938]: J. Singer, "A Theorem in Finite Projective Geometry and Some Applications to Number Theory," Transactions of the American Mathematical Society, vol. 43, no. 2, p. pp. 377–85, 1938. URL (accessed Dec 1, 2022): https://www.ams.org/journals/tran/1938-043-03/S0002-9947-1938-1501951-4/S0002-9947-1938-1501951-4.pdf