Geodesic
Fermat test with Gaussian base and Gaussian pseudoprimes
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 4, pp. 969-982 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

The structure of the group $(\mathbb {Z}/n\mathbb {Z})^\star $ 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{\rm i}\in \mathbb {Z}[{\rm i}]/n\mathbb {Z}[{\rm i}]\colon a^2+b^2\equiv 1\pmod n\}$. In particular, we characterize Gaussian Carmichael numbers via a Korselt's criterion and present their relation with Gaussian cyclic numbers. Finally, we present the relation between Gaussian Carmichael number and 1-Williams numbers for numbers $n \equiv 3\pmod 4$. There are also no known composite numbers less than $10^{18}$ in this family that are both pseudoprime to base $1+2{\rm i}$ and 2-pseudoprime.
The structure of the group $(\mathbb {Z}/n\mathbb {Z})^\star $ 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{\rm i}\in \mathbb {Z}[{\rm i}]/n\mathbb {Z}[{\rm i}]\colon a^2+b^2\equiv 1\pmod n\}$. In particular, we characterize Gaussian Carmichael numbers via a Korselt's criterion and present their relation with Gaussian cyclic numbers. Finally, we present the relation between Gaussian Carmichael number and 1-Williams numbers for numbers $n \equiv 3\pmod 4$. There are also no known composite numbers less than $10^{18}$ in this family that are both pseudoprime to base $1+2{\rm i}$ and 2-pseudoprime.
DOI : 10.1007/s10587-015-0221-2
Classification : 11A25, 11A51, 11D45
Keywords: Gaussian integer; Fermat test; pseudoprime 
@article{10_1007_s10587_015_0221_2,
     author = {Grau, Jos\'e Mar{\'\i}a and Oller-Marc\'en, Antonio M. and Rodr{\'\i}guez, Manuel and Sadornil, Daniel},
     title = {Fermat test with {Gaussian} base and {Gaussian} pseudoprimes},
     journal = {Czechoslovak Mathematical Journal},
     pages = {969--982},
     year = {2015},
     volume = {65},
     number = {4},
     doi = {10.1007/s10587-015-0221-2},
     mrnumber = {3441329},
     zbl = {06537704},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0221-2/}
}
TY  - JOUR
AU  - Grau, José María
AU  - Oller-Marcén, Antonio M.
AU  - Rodríguez, Manuel
AU  - Sadornil, Daniel
TI  - Fermat test with Gaussian base and Gaussian pseudoprimes
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 969
EP  - 982
VL  - 65
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0221-2/
DO  - 10.1007/s10587-015-0221-2
LA  - en
ID  - 10_1007_s10587_015_0221_2
ER  - 
%0 Journal Article
%A Grau, José María
%A Oller-Marcén, Antonio M.
%A Rodríguez, Manuel
%A Sadornil, Daniel
%T Fermat test with Gaussian base and Gaussian pseudoprimes
%J Czechoslovak Mathematical Journal
%D 2015
%P 969-982
%V 65
%N 4
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0221-2/
%R 10.1007/s10587-015-0221-2
%G en
%F 10_1007_s10587_015_0221_2
Grau, José María; Oller-Marcén, Antonio M.; Rodríguez, Manuel; Sadornil, Daniel. Fermat test with Gaussian base and Gaussian pseudoprimes. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 4, pp. 969-982. doi: 10.1007/s10587-015-0221-2

[1] Alford, W. R., Granville, A., Pomerance, C.: There are infinitely many Carmichael numbers. Ann. Math. (2) 139 (1994), 703-722. | MR | Zbl

[2] Borwein, D., Maitland, C., Skerritt, M.: Computation of an improved lower bound to Giuga's primality conjecture. Integers (electronic only) 13 (2013), Paper A67, 14 pages. | MR | Zbl

[3] Burcsi, P., Czirbusz, S., Farkas, G.: Computational investigation of Lehmer's totient problem. Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 35 (2011), 43-49. | MR | Zbl

[4] Carmichael, R. D.: Note on a new number theory function. Amer. Math. Soc. Bull. (2) 16 (1910), 232-238. | DOI | MR

[5] Cross, J. T.: The Euler $\phi$-function in the Gaussian integers. Am. Math. Mon. 90 (1983), 518-528. | DOI | MR | Zbl

[6] Echi, O.: Williams numbers. C. R. Math. Acad. Sci., Soc. R. Can. 29 (2007), 41-47. | MR | Zbl

[7] Galway, W.: Tables of pseudoprimes and related data. http://www.cecm.sfu.ca/Pseudoprimes/</b>

[8] Giuga, G.: Su una presumibile proprietà caratteristica dei numeri primi. Ist. Lombardo Sci. Lett., Rend., Cl. Sci. Mat. Natur. (3) 14 (1951), 511-528 Italian. | MR | Zbl

[9] Goldman, J. R.: Numbers of solutions of congruences: Poincaré series for strongly nondegenerate forms. Proc. Am. Math. Soc. 87 (1983), 586-590. | MR | Zbl

[10] Hardy, G. H., Wright, E. M.: An Introduction to the Theory of Numbers. Oxford University Press Oxford (2008). | MR | Zbl

[11] Lehmer, D. H.: On Euler's totient function. Bull. Am. Math. Soc. 38 (1932), 745-751. | DOI | MR | Zbl

[12] Lemmermeyer, F.: Conics---a poor man's elliptic curves. Preprint at http://www.fen.bilkent.edu.tr/ {franz/publ/conics.pdf} arXiv:math/0311306v1[math.NT].

[13] Pinch, R. G. E.: Absolute quadratic pseudoprimes. Proc. of Conf. on Algorithmic Number Theory. TUCS General Publications 46 A.-M. Ernvall-Hytönen at al. (2007), 113-128. http://tucs.fi/publications/view/?id=pErJuKaLe07a&amp;amp;table=proceeding

[14] C. Pomerance, J. L. Selfridge, S. S. Wagstaff, Jr.: The pseudoprimes to $25\cdot 10^9$. Math. Comput. 35 (1980), 1003-1026. | MR | Zbl

[15] Schettler, J.: Lehmer's totient problem and Carmichael numbers in a PID. http://math.ucsb.edu/ {jcs/Schettler.pdf}.

[16] Silverman, J. H.: Elliptic Carmichael numbers and elliptic Korselt criteria. Acta Arith. 155 (2012), 233-246. | DOI | MR | Zbl

[17] Sloane, N. J. A.: The On-Line Encyclopedia of Integer Sequences. http://www.oeis.org | Zbl

[18] Steele, G. A.: Carmichael numbers in number rings. J. Number Theory 128 (2008), 910-917. | DOI | MR | Zbl

[19] Szele, T.: Über die endlichen Ordnungszahlen zu denen nur eine Gruppe gehört. Comment. Math. Helv. 20 (1947), 265-267 German. | DOI | MR | Zbl

[20] Tarry, G., Franel, I., Korselt, A. R., Vacca, G.: Problème chinois. L'intermédiaire des mathématiciens 6 (1899), 142-144 French www.oeis.org/wiki/File:Problème\_chinois.pdf.

[21] Williams, H. C.: On numbers analogous to the Carmichael numbers. Can. Math. Bull. 20 (1977), 133-143. | DOI | MR | Zbl

Cité par Sources :