Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T20:12:46.939Z Has data issue: false hasContentIssue false
  • English
  • Français

SYLOW p-PSEUDOPRIMES TO SEVERAL BASES FOR SEVERAL PRIMES p

Part of: Computational number theory Elementary number theory

Published online by Cambridge University Press:  05 October 2009

ZHENXIANG ZHANG  and
RUIRUI XIE
ZHENXIANG ZHANG*
Affiliation:
Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, PR China (email: [email protected], [email protected])
RUIRUI XIE
Affiliation:
Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, PR China (email: [email protected])
*
✉For correspondence; e-mail: [email protected], [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Browkin [‘Some new kinds of pseudoprimes’, Math. Comp. 73 (2004), 1031–1037] gave examples of strong pseudoprimes to many bases which are not Sylow p-pseudoprimes to two bases only, where p=2 or 3. In contrast to Browkin’s examples, Zhang [‘Notes on some new kinds of pseudoprimes’, Math. Comp. 75 (2006), 451–460] gave facts and examples which are unfavorable for Browkin’s observation on detecting compositeness of odd composite numbers. In particular, Zhang gave a Sylowp-pseudoprime (with 27 decimal digits) to the first 6 prime bases for all the first 6 primes p, and conjectured that for any k≥1, there would exist Sylow p-pseudoprimes to the first k prime bases for all the first k primes p. In this paper we tabulate 27 Sylow p-pseudoprimes less than 1036 to the first 7 prime bases for all the first 7 primes p (two of which are Sylow p-pseudoprimes to the first 7 prime bases for all the first 8 primes p). We describe the procedure for finding these numbers. The main tools used in our method are the cubic residue characters and the Chinese remainder theorem.

Keywords

strong pseudoprimesMiller testsSylow p-pseudoprimescubic residue charactersChinese remainder theorem

MSC classification

Secondary: 11A15: Power residues, reciprocity 11Y11: Primality
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 81 , Issue 1 , February 2010 , pp. 165 - 176
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2009

Footnotes

Research supported by the NSF of China Grant 10071001.

References

[1]Bleichenbacher, D., ‘Efficiency and security of cryptosystems based on number theory’, ETH PhD Dissertation 11404, Swiss Federal Institute of Technology, Zurich, 1996.Google Scholar
[2]Bressoud, D. M. and Wagon, S., A Course in Computational Number Theory (Key College Publishing, Emeryville, CA, 2000).Google Scholar
[3]Browkin, J., ‘Some new kinds of pseudoprimes’, Math. Comp. 73(246) (2004), 1031–1037; Math. Comp. 74 (2005), 1573 (Erratum).CrossRefGoogle Scholar
[4]Crandall, R. and Pomerance, C., Prime Numbers, a Computational Perspective, 2nd edn (Springer, New York, 2005).Google Scholar
[5]Ireland, K. and Rosen, M., A Classical Introduction to Modern Number Theory, 2nd edn Graduate Texts in Mathematics, 84 (Springer, New York, 1990).CrossRefGoogle Scholar
[6]Jaeschke, G., ‘On strong pseudoprimes to several bases’, Math. Comp. 61 (1993), 915–926.CrossRefGoogle Scholar
[7]Miller, G., ‘Riemann’s hypothesis and tests for primality’, J. Comput. System Sci. 13 (1976), 300–317.CrossRefGoogle Scholar
[8]Pinch, R. G. E., ‘The Carmichael numbers up to 1016’, Preprint, 1998. http://www.chalcedon.demon.co.uk/carpsp.html.Google Scholar
[9]Pomerance, C., Selfridge, J. L. and Wagstaff, S. S. Jr, ‘The pseudoprimes to 25⋅109’, Math. Comp. 35 (1980), 1003–1026.Google Scholar
[10]Zhang, Z., ‘Finding strong pseudoprimes to several bases’, Math. Comp. 70 (2001), 863–872. http://www.ams.org/journal-getitem?pii=S0025-5718-00-01215-1.CrossRefGoogle Scholar
[11]Zhang, Z., ‘Finding C 3-strong pseudoprimes’, Math. Comp. 74 (2005), 1009–1024. http://www.ams.org/mcom/2005-74-250/S0025-5718-04-01693-X/home.html.CrossRefGoogle Scholar
[12]Zhang, Z., ‘Notes on some new kinds of pseudoprimes’, Math. Comp. 75(253) (2006), 451–460. http://www.ams.org/mcom/2006-75-253/S0025-5718-05-01775-8/home.html.CrossRefGoogle Scholar
[13]Zhang, Z., ‘Two kinds of strong pseudoprimes up to 1036’, Math. Comp. 76(260) (2007), 2095–2107. http://www.ams.org/mcom/2007-76-260/S0025-5718-07-01977-1/home.html.CrossRefGoogle Scholar
[14]Zhang, Z. and Tang, M., ‘Finding strong pseudoprimes to several bases. II’, Math. Comp. 72 (2003), 2085–2097. http://www.ams.org/journal-getitem?pii=S0025-5718-03-01545-X.CrossRefGoogle Scholar