Primes in quadratic unique factorization domains (Q301417)

The present paper studies some questions related with prime elements in the integer ring \(\mathcal{O}_K\)\, of a quadratic number field \(K=\sqrt{\theta}\), \(\theta\) a squarefree integer, assuming \(\mathcal{O}_K\)\, is a unique factorization domain (and then a principal ideal domain). In fact the paper extends to \(\mathcal{O}_K\)\, some well-known criterions of primality in natural numbers and it proposes a RSA-cryptosystem in that ring.NEWLINENEWLINESection 3 generalizes the primality criteria of Miller, Euler, Lucas and Pocklington to elements \(N\in \mathcal{O}_K\). The statements of those criteria look very similar to the classical (with \(N\), as exponent, substituted by their norm \(\text{Nm}(N)\)). Section 4 proves that, in the case \(\mathcal{O}_K\)\, Euclidean imaginary (what happens for \(\theta= -1,-2.-3,-7,-11)\), the Miller's criterion provides an efficient primality test (Theorem 5), similar to the classical Miller-Rabin test, see [\textit{G. L. Miller}, J. Comput. Syst. Sci. 13, 300--317 (1976; Zbl 0349.68025)] and [\textit{M. O. Rabin}, J. Number Theory 12, 128--138 (1980; Zbl 0426.10006)]. The probability that \(N\) is composite despite passing the test for \(k\) random basis is at most \(1/2^k\).NEWLINENEWLINEFinally Section 5, also for \(\mathcal{O}_K\)\, Euclidean imaginary, describes an efficient RSA-like cryptosystem and studies its security: the weakness of a low private key (Theorem 7) and the iterated encryption attack (Theorem 8).