A Deterministic Cryptographic Prime Generation Chain over Monogenic Cubic Number Fields and their Generalizations

Abstract

Generating primes is a fundamental problem in modern cryptography. Deterministic primality tests work well for special integers such as Mersenne or Proth primes, but these forms are quite restrictive. In this paper, we give a direct method to construct new primes from known ones. Starting with a seed prime $q\equiv 1(\mathrm{mod}3)$, we construct an integer $N\equiv 1(\mathrm{mod}3)$ satisfying $(2N+1{)}^2\equiv -3(\mathrm{mod}q)$. We then prove that $N$ is prime using the structure of monogenic pure cubic fields $K=\mathbb{Q}(\sqrt[3]{d})$. The resulting test requires only a single modular exponentiation and runs in $\tilde{\mathcal{O}}({\log }^{2}N)$ time. Finally, we show how this construction extends to pure number fields of arbitrary prime degree.

Feedback is welcome