| Title:
|
Fermat test with Gaussian base and Gaussian pseudoprimes (English) |
| Author:
|
Grau, José María |
| Author:
|
Oller-Marcén, Antonio M. |
| Author:
|
Rodríguez, Manuel |
| Author:
|
Sadornil, Daniel |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
4 |
| Year:
|
2015 |
| Pages:
|
969-982 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
Gaussian integer |
| Keyword:
|
Fermat test |
| Keyword:
|
pseudoprime |
| MSC:
|
11A25 |
| MSC:
|
11A51 |
| MSC:
|
11D45 |
| idZBL:
|
Zbl 06537704 |
| idMR:
|
MR3441329 |
| DOI:
|
10.1007/s10587-015-0221-2 |
| . |
| Date available:
|
2016-01-13T09:09:35Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144786 |
| . |
| Reference:
|
[1] Alford, W. R., Granville, A., Pomerance, C.: There are infinitely many Carmichael numbers.Ann. Math. (2) 139 (1994), 703-722. Zbl 0816.11005, MR 1283874 |
| Reference:
|
[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. Zbl 1284.11002, MR 3118385 |
| Reference:
|
[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. Zbl 1240.11005, MR 2894552 |
| Reference:
|
[4] Carmichael, R. D.: Note on a new number theory function.Amer. Math. Soc. Bull. (2) 16 (1910), 232-238. MR 1558896, 10.1090/S0002-9904-1910-01892-9 |
| Reference:
|
[5] Cross, J. T.: The Euler $\phi$-function in the Gaussian integers.Am. Math. Mon. 90 (1983), 518-528. Zbl 0525.12001, MR 0717096, 10.2307/2322785 |
| Reference:
|
[6] Echi, O.: Williams numbers.C. R. Math. Acad. Sci., Soc. R. Can. 29 (2007), 41-47. Zbl 1204.11185, MR 2367725 |
| Reference:
|
[7] Galway, W.: Tables of pseudoprimes and related data. http://www.cecm.sfu.ca/Pseudoprimes/.. |
| Reference:
|
[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. Zbl 0045.01801, MR 0046381 |
| Reference:
|
[9] Goldman, J. R.: Numbers of solutions of congruences: Poincaré series for strongly nondegenerate forms.Proc. Am. Math. Soc. 87 (1983), 586-590. Zbl 0511.12014, MR 0687622 |
| Reference:
|
[10] Hardy, G. H., Wright, E. M.: An Introduction to the Theory of Numbers.Oxford University Press Oxford (2008). Zbl 1159.11001, MR 2445243 |
| Reference:
|
[11] Lehmer, D. H.: On Euler's totient function.Bull. Am. Math. Soc. 38 (1932), 745-751. Zbl 0005.34302, MR 1562500, 10.1090/S0002-9904-1932-05521-5 |
| Reference:
|
[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]. |
| Reference:
|
[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&table=proceeding. |
| Reference:
|
[14] C. Pomerance, J. L. Selfridge, S. S. Wagstaff, Jr.: The pseudoprimes to $25\cdot 10^9$.Math. Comput. 35 (1980), 1003-1026. Zbl 0444.10007, MR 0572872 |
| Reference:
|
[15] Schettler, J.: Lehmer's totient problem and Carmichael numbers in a PID. http://math.ucsb.edu/ {jcs/Schettler.pdf}.. |
| Reference:
|
[16] Silverman, J. H.: Elliptic Carmichael numbers and elliptic Korselt criteria.Acta Arith. 155 (2012), 233-246. Zbl 1304.11047, MR 2983450, 10.4064/aa155-3-1 |
| Reference:
|
[17] Sloane, N. J. A.: The On-Line Encyclopedia of Integer Sequences.http://www.oeis.org. Zbl 1159.11327 |
| Reference:
|
[18] Steele, G. A.: Carmichael numbers in number rings.J. Number Theory 128 (2008), 910-917. Zbl 1176.11049, MR 2400049, 10.1016/j.jnt.2007.08.009 |
| Reference:
|
[19] Szele, T.: Über die endlichen Ordnungszahlen zu denen nur eine Gruppe gehört.Comment. Math. Helv. 20 (1947), 265-267 German. Zbl 0034.30502, MR 0021934, 10.1007/BF02568132 |
| Reference:
|
[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. |
| Reference:
|
[21] Williams, H. C.: On numbers analogous to the Carmichael numbers.Can. Math. Bull. 20 (1977), 133-143. Zbl 0368.10011, MR 0447099, 10.4153/CMB-1977-025-9 |
| . |
