Dissertation > Excellent graduate degree dissertation topics show

Finding Carmichael Numbers which are Strong Pseudoprimes

Author: JiYiGui
Tutor: ZhangZhenXiang
School: Anhui Normal University
Course: Applied Mathematics
Keywords: Carmichael numbers Rabin-Miller test strong pseudoprimes primality testing computational number theory
CLC: O156
Type: Master's thesis
Year: 2006
Downloads: 38
Quote: 0
Read: Download Dissertation

Abstract


(Department of Mathematics, Anhui Normal University, Wuhu 241000)Abstract: Define ψm to be the smallest strong pseudoprimes to all the first m prime bases. If we know the exact value of ψm, we will have, for integers < ψm, a deterministic primality testing algorithm which is not only easier to implement but also faster than either the Jacobi Sum test, the elliptic curve test, or the AKS algorithm. Thanks to Pomer-ance et al. [Math. Comp. Vol.35, 1980, pp.1003-1026; MR 82g:10030] and Jaeschke [Math. Comp. Vol.61, 1993, pp.915-926; MR 94d:11004], ψm are known for 1 ≤ m ≤ 8. Zhang and Tang [Math. Comp. Vol.72, 2003, pp.2085-2097; MR 2004c:11008] used a fast algorithm to find all C3-numbers < 1020 which are also strong pseudoprimes to the first 5 prime bases. Here C3-numbers mean Carmichael numbers N = q1q2q3 with 3 prime factors q1 = q2 = q3 = 3 mod 4. （Such numbers have a high probability to be strong pseudoprimes to more bases.） They gave a conjected value for ψ9, ψ10 and ψ11:ψ9 = ψ10 = ψ11 = 3825 12305 65464 13051 = 149491 ? 747451 ? 34233211,and gave reasons to support the conjecture. Not long later, Zhang [Math. Comp. Vol.74, 2005, pp.1009-1024; MR 2114662 （2005k:11243）] used another new method to find almost all C3-numbers < 1024, which are also strong pseudoprime to the first 9 prime bases. He gave a conjected valu of ψ12:ψ12 = 3186 65857 83403 11511 67461 = 399165290221 ? 798330580441,and gave reasons to support the conjecture.In this paper we enlighted by the work of Zhang, correspondingly define C3,1-numbers and C3,2 -numbers to be Carmichael numbers N = 919293 with 3 prime factors q1 = q2 = q3 = 5 mod 8; and q1 = q2 = 3 mod 4,q3 = 9 mod 16 respectively. （Such numbers also have a high probability to be strong pseudoprimes, only lower than C3-numbers of 3-factors Carmichael numbers.） We first give sufficient and necessary conditions for such numbers; then give algorithms for finding such numbers. We find all C3,1-numbers < 1024 which are strong pseudoprmes to 2, there are 55971 numbers in total, only 1 of them is a strong pseudoprmes to the first 8 prime bases; no C3,1-strong pseudoprmes to the first 9 prime bases are found. We also find all C3,2-numbers < 1024 which are strong pseudoprmes to 2, there are 11327 numbers in total, only 1 of them is a strong pseudoprme to the first 5 prime bases; no C3,2 -strong pseudoprmes to the first 6 prime bases are found. These data enhence the reliability of the conjectured values of ψ9, ψ10, ψ11 and ψ12 given by Zhang.

Related Dissertations

  1. The RSA algorithm primality problem,TN918
  2. Several Problems in Computational Number Theory,O156
  3. Research on Some Algorithms for Public-Key Cryptosystems,TN918.1
  4. Dirichlet Series and Random Dirichlet Series of Infinite Order,O156.4
  5. Interrelated Almost Periodicity of the Solutions of DIRICHLET Problem,O156.4
  6. Green function of the ball four yuan Monge-Ampere equation,O156
  7. Odd values ??of the generalized Euler function (?) _e (N),O156
  8. The Dirichlet Series and Random Dirichlet Series of Zero Order,O156.4
  9. The Growth of Dirichlet Series and Random Dirichlet Series of Finite Order,O156.4
  10. Bounded Sequence of Integers and Transcendence of Real Numbers,O156
  11. The Lévy Constants of Some Transcendental Numbers,O156
  12. Research on Square Free Numbers and Smarandache Functions,O156.1
  13. Mean Value on Some Arithmetical Functions,O156.4
  14. Integral Points in the Scheme of the Arithmetic Type,O156.2
  15. Growth of the Generalized Dirichlet Series,O156.4
  16. Two Transform Formulas of Bilateral Basic Hypergeometric Series and Their Applications,O156
  17. On Equation of Ab = (nα),O156.4
  18. The Mean Value Problems of Some Functions and All Solutions of the Equation,O156.4
  19. On the Maximum and Minimum Component of the Standard Compositon of An Integer,O156.4
  20. The Smarandache function equation as well as the mean Research,O156.4
  21. The mean value of the Smarandache function and solvability,O156.4

CLC: > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Number Theory
© 2012 www.DissertationTopic.Net  Mobile