Fermat test with Gaussian base and Gaussian pseudoprimes

José María Grau; Antonio M. Oller-Marcén; Manuel Rodríguez; Daniel Sadornil

Czechoslovak Mathematical Journal (2015)

  • Volume: 65, Issue: 4, page 969-982
  • ISSN: 0011-4642

Abstract

top
The structure of the group ( ℤ / n ℤ ) ☆ 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 𝒢 n : = { a + b i ∈ ℤ [ i ] / n ℤ [ i ] : a 2 + b 2 ≡ 1 ( mod 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 ≡ 3 ( mod 4 ) . There are also no known composite numbers less than 10 18 in this family that are both pseudoprime to base 1 + 2 i and 2-pseudoprime.

How to cite

top

Grau, José María, et al. "Fermat test with Gaussian base and Gaussian pseudoprimes." Czechoslovak Mathematical Journal 65.4 (2015): 969-982. <http://eudml.org/doc/276094>.

@article{Grau2015,
abstract = {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:=\lbrace a+b\{\rm i\}\in \mathbb \{Z\}[\{\rm i\}]/n\mathbb \{Z\}[\{\rm i\}]\colon a^2+b^2\equiv 1\hspace\{4.44443pt\}(\@mod \; n)\rbrace $. 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\hspace\{4.44443pt\}(\@mod \; 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.},
author = {Grau, José María, Oller-Marcén, Antonio M., Rodríguez, Manuel, Sadornil, Daniel},
journal = {Czechoslovak Mathematical Journal},
keywords = {Gaussian integer; Fermat test; pseudoprime},
language = {eng},
number = {4},
pages = {969-982},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Fermat test with Gaussian base and Gaussian pseudoprimes},
url = {http://eudml.org/doc/276094},
volume = {65},
year = {2015},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 4
SP - 969
EP - 982
AB - 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:=\lbrace a+b{\rm i}\in \mathbb {Z}[{\rm i}]/n\mathbb {Z}[{\rm i}]\colon a^2+b^2\equiv 1\hspace{4.44443pt}(\@mod \; n)\rbrace $. 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\hspace{4.44443pt}(\@mod \; 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.
LA - eng
KW - Gaussian integer; Fermat test; pseudoprime
UR - http://eudml.org/doc/276094
ER -

References

top
  1. Alford, W. R., Granville, A., Pomerance, C., There are infinitely many Carmichael numbers, Ann. Math. (2) 139 (1994), 703-722. (1994) Zbl0816.11005MR1283874
  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. (2013) Zbl1284.11002MR3118385
  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. (2011) Zbl1240.11005MR2894552
  4. Carmichael, R. D., 10.1090/S0002-9904-1910-01892-9, Amer. Math. Soc. Bull. (2) 16 (1910), 232-238. (1910) MR1558896DOI10.1090/S0002-9904-1910-01892-9
  5. Cross, J. T., 10.2307/2322785, Am. Math. Mon. 90 (1983), 518-528. (1983) Zbl0525.12001MR0717096DOI10.2307/2322785
  6. Echi, O., Williams numbers, C. R. Math. Acad. Sci., Soc. R. Can. 29 (2007), 41-47. (2007) Zbl1204.11185MR2367725
  7. Galway, W., Tables of pseudoprimes and related data. http://www.cecm.sfu.ca/Pseudoprimes/, . 
  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. (1951) Zbl0045.01801MR0046381
  9. Goldman, J. R., Numbers of solutions of congruences: Poincaré series for strongly nondegenerate forms, Proc. Am. Math. Soc. 87 (1983), 586-590. (1983) Zbl0511.12014MR0687622
  10. Hardy, G. H., Wright, E. M., An Introduction to the Theory of Numbers, Oxford University Press Oxford (2008). (2008) Zbl1159.11001MR2445243
  11. Lehmer, D. H., 10.1090/S0002-9904-1932-05521-5, Bull. Am. Math. Soc. 38 (1932), 745-751. (1932) Zbl0005.34302MR1562500DOI10.1090/S0002-9904-1932-05521-5
  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&table=proceeding. (2007) 
  14. C. Pomerance, J. L. Selfridge, S. S. Wagstaff, Jr., The pseudoprimes to 25 · 10 9 , Math. Comput. 35 (1980), 1003-1026. (1980) Zbl0444.10007MR0572872
  15. Schettler, J., Lehmer's totient problem and Carmichael numbers in a PID. http://math.ucsb.edu/ {jcs/Schettler.pdf}, . 
  16. Silverman, J. H., 10.4064/aa155-3-1, Acta Arith. 155 (2012), 233-246. (2012) Zbl1304.11047MR2983450DOI10.4064/aa155-3-1
  17. Sloane, N. J. A., The On-Line Encyclopedia of Integer Sequences, http://www.oeis.org. Zbl1159.11327
  18. Steele, G. A., 10.1016/j.jnt.2007.08.009, J. Number Theory 128 (2008), 910-917. (2008) Zbl1176.11049MR2400049DOI10.1016/j.jnt.2007.08.009
  19. Szele, T., 10.1007/BF02568132, Comment. Math. Helv. 20 (1947), 265-267 German. (1947) Zbl0034.30502MR0021934DOI10.1007/BF02568132
  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. (1899) 
  21. Williams, H. C., 10.4153/CMB-1977-025-9, Can. Math. Bull. 20 (1977), 133-143. (1977) Zbl0368.10011MR0447099DOI10.4153/CMB-1977-025-9

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.