### Fermat test with Gaussian base and Gaussian pseudoprimes

José María Grau, Antonio M. Oller-Marcén, Manuel Rodríguez, Daniel Sadornil (2015)

Czechoslovak Mathematical Journal

Similarity:

The structure of the group ${(\mathbb{Z}/n\mathbb{Z})}^{\u2606}$ and Fermat’s little theorem are the basis for some of the best-known primality testing algorithms. Many related concepts arise: Euler’s totient function and Carmichael’s lambda function, Fermat pseudoprimes, Carmichael and cyclic numbers, Lehmer’s totient problem, Giuga’s conjecture, etc. In this paper, we present and study analogues to some of the previous concepts arising when we consider the underlying group ${\mathcal{G}}_{n}:=\{a+b\mathrm{i}\in \mathbb{Z}\left[\mathrm{i}\right]/n\mathbb{Z}\left[\mathrm{i}\right]:{a}^{2}+{b}^{2}\equiv 1\phantom{\rule{4.44443pt}{0ex}}(mod\phantom{\rule{0.277778em}{0ex}}n)\}$. In particular, we characterize Gaussian Carmichael...