1. Quotes from Renowned Mathematicians 8
2. Keyword 10
3. Introduction 12
3.1. The Aim of Thesis 12
3.2. The Scope of Thesis 12
3.3. Research Hierarchical Diagram 12
4. Related Math Branches or Sub-Disciples 13
5. Presentation Styles 13
6. Structure of Writing 16
7. Styles 19
8. Definitions. Terminology, Signs and Symbols 20
8.1. Alphabets and Signs 20
8.1.1. Latin 20
8.1.2. Greek 21
8.1.3. Hebrew 21
8.1.4. Russian 21
8.2. Nomenclature 21
8.3. Notation 22
8.4. Definitions 23
8.5. List of theorems, formulars and equations 23
8.6. List of abbreviations 23
8.7. List of people mentioned in the book 24
8.8. Index 24
8.9. Explanations 24
8.10. Fonts 24
8.11. List of symbols 25
8.12. Sub and super scripts 25
8.13. Marks 25
8.14. 词冠??? 25
8.15. UNITS 26
8.16. Units designation 26
8.17. Constants 26
9. Comparisons of Algorithm 27
10. Intro 27
10.1. TOC for Introduction to Algorithms 27
11. Recent developments in primality testing 32
11.1. Recent developments in primality testing 33
12. Comparison / Benchmarking for Primality Testing 34
12.1. Comparison study for Primality testing using Mathematica 34
13. Deterministic Primality Testing 35
13.1. AKS primality test 35
13.2. APR - Adleman–Pomerance–Rumely primality test 35
13.3. Atkin sieve 36
13.3.1. Contents 37
13.3.2. Algorithm 37
13.3.3. Pseudocode 38
13.3.4. Explanation 39
13.3.5. Computational complexity 39
13.3.6. See also 39
13.3.7. References 40
13.4. Bhattacharjee and Pandey 40
13.5. Brillhart, Lehmer, Selfridge Test based on Lucas Test 42
13.6. Cyclotomic Deterministic Primality Test Cyclotomy 42
13.7. Demytko deterministic primality test method 43
13.8. Elliptic curve methods 43
13.9. Eratosthenes Sieve 44
13.9.1. Contents 45
13.9.2. Algorithm description 45
13.9.3. Example 47
13.9.4. Algorithm complexity 47
13.9.5. Implementation 48
13.9.6. Arithmetic progressions 48
13.9.7. Euler's sieve 48
13.9.8. See also 49
13.9.9. References 49
13.10. Goldwasser Kilian Algorithm 49
13.11. Jacobi Sums 50
13.12. Lucas素性测定算法 50
13.12.1. Contents 51
13.12.2. Concepts 51
13.12.3. Example 52
13.12.4. Algorithm 53
13.12.5. See also 53
13.13. Lucas-Lehmer测试 53
13.13.1. 梅森素数判定算法Lucas-Lehmer测试 54
13.13.2. Contents 55
13.13.3. The test 55
13.13.4. Time complexity 56
13.13.5. Examples 57
13.13.6. Proof of correctness 58
13.13.7. Applications 61
13.13.8. See also 62
13.14. Lucas–Lehmer–Riesel 62
13.14.1. Contents 63
13.14.2. The algorithm 63
13.14.3. Finding the starting value 63
13.14.4. How does the test work? 63
13.14.5. LLR software 64
13.14.6. References 64
13.14.7. External links 64
13.14.8. 推广的Lucas型素性测定算法 65
13.14.9. Massey–Omura–Kryptosystem 65
13.15. Miller-Primzahltest 65
13.16. Pocklington Lehmer primality test 66
13.16.1. Contents 67
13.16.2. Pocklington criterion 67
13.16.3. Generalized Pocklington method 68
13.16.4. The test 69
13.16.5. Example 69
13.17. Proth deterministic primality test method 71
13.18. Sundaram sieve 71
13.18.1. Contents 72
13.18.2. Algorithm 72
13.18.3. Correctness 72
13.18.4. Computational complexity 73
13.18.5. See also 73
13.18.6. References 73
13.19. Trial division 73
13.20. Ward’s primality test 74
13.21. Wilson's Primality Test威尔逊判别法 74
14. Randomized /Probabilistic/ Probable / Provable / Primality Testing 75
14.1. Adelman-Huang algorithm 75
14.2. Agrawal-Biswas algorithm or Agarwal-Biswas Probabilistic Testing 76
14.3. AKS parallel sorting algorithm of Ajtai, Koml´os and Szemer´edi 77
14.4. ALI primality test 77
14.5. APR Test 77
14.6. APRT-CL (or APRCL) 77
14.7. 素性测试的ARCL算法 78
14.8. Baillie–PSW 78
14.9. BPP algorithm 79
14.10. Baillie and Wagstaff Method 81
14.11. Chen--Kao and Lewin--Vadhan tests 81
14.12. Chinese Primality Test 81
14.13. Chinese Remaindering 81
14.14. Cohen-Lenstra Method 82
14.15. Colin Plumb primality test (Euler Criterion) 82
14.16. Combination Algorithm 83
14.17. Cyclotomic Probabilistic Primality Test 83
14.18. ECPP Elliptic Curve Primality Proving 84
14.19. Elliptic Curve Primality Testing 85
14.19.1. Proposition 85
14.19.2. Proof 86
14.19.3. Goldwasser–Kilian algorithm 87
14.19.4. Problems with the algorithm 88
14.19.5. Atkin–Morain elliptic curve primality test (ECPP) 88
14.19.6. The test 89
14.19.7. Complex multiplication method 90
14.19.8. Discussion 90
14.19.9. Example of Atkin–Morain ECPP 91
14.19.10. Complexity and running times 92
14.19.11. Conjecture 92
14.19.12. Conjecture 2 93
14.19.13. Primes of special form 93
14.19.14. Group structure of E(FN) 94
14.19.15. Theorem 1 94
14.19.16. Theorem 2 94
14.19.17. Theorem 3 94
14.19.18. Theorem 4 95
14.19.19. The algorithm 95
14.19.20. Justification of the algorithm 96
14.19.21. References 96
14.20. Demytko 96
14.21. Euler Test 98
14.22. Fermat素性测试 98
14.22.1. Contents 99
14.22.2. Concept 99
14.22.3. Example 100
14.22.4. Algorithm and running time 100
14.22.5. Flaw 100
14.22.6. Applications 101
14.23. Fermat-Euler 102
14.24. Frobenius pseudoprimality test 102
14.25. Goldwasser Kilian Algorithm 102
14.26. Gordon‟s algorithm 102
14.27. 雅克比和素性判别方法 103
14.28. Konyagin – Pomerance n-1 Test 103
14.29. Lehmann 103
14.30. Maurer‟s algorithm 104
14.31. Miller-Rabin / Rabin-Miller素性测试算法Miller-Rabin Compositeness Test 105
14.31.1. 快速判定素数-----Miller-Rabin算法 105
14.31.2. Miller-Rabin Algorithm 106
14.31.3. Miller-Rabbin素性测试[ZJUT1517] 107
14.31.4. Rabin-Miller 109
14.31.5. Contents 110
14.31.6. Concepts 110
14.31.7. Example 112
14.31.8. Algorithm and running time 112
14.31.9. Accuracy of the test 113
14.31.10. Deterministic variants of the test 114
14.31.11. Notes 115
14.32. MONTE CARLO PRIMALITY TESTS 115
14.32.1. A NOTE ON MONTE CARLO PRIMALITY TESTS AND ALGORITHMIC INFORMATION THEORY 115
14.33. Pépin's 116
14.33.1. Contents 117
14.33.2. Description of the test 117
14.33.3. Proof of correctness 117
14.33.4. References 118
14.34. Proth's theorem 118
14.34.1. Contents 119
14.34.2. Numerical examples 119
14.34.3. History 120
14.34.4. See also 120
14.34.5. References 120
14.35. Random Quadratic Frobenius Test (RQFT) 121
14.36. Solovay- Strassen算法 121
14.36.1. Solovay-Strassen primality test. 121
14.36.2. Solovag-Strasson 122
14.36.3. Contents 123
14.36.4. Concepts 123
14.36.5. Example 124
14.36.6. Algorithm and running time 124
14.36.7. Accuracy of the test 125
14.36.8. Average-case behaviour 126
14.36.9. Complexity 126
14.37. Square Root Compositeness Theorem 126
14.38. Schwartz--Zippel test 127
15. Papers of Others 128
15.1. 素性检测算法研究及其在现代密码学中的应用 128
16. Math Tools 131
16.1. Axiom 131
16.2. Bignum 131
16.3. Derive 131
16.4. GMP Library 131
16.5. GNU Octave 131
16.6. Kant 132
16.7. LiDIA 132
16.8. Lisp 132
16.9. Macsyma 132
16.10. Magma 132
16.11. Maple 133
16.12. MathCad 133
16.13. Mathematica 133
16.14. Matlab 133
16.15. Maxima 133
16.16. MIRACL 134
16.17. MuPAD 134
16.18. NTL library 134
16.19. OpenMP 134
16.20. Pari -GP 134
16.21. Reduce 135
16.22. Sage 135
16.23. Simath 135
16.24. Ubasic 135
17. COMPARISONS 136
18. MY IDEAS FOR FURTHER IMPROVEMENT OF COMPLEXITY 136
19. RESOURCES 137
19.1. MAJOR NUMBER THEORISTS 137
19.2. KEY UNIVERSITIES 137
19.3. KEY RESEARCH INSTITUTIONS 137
19.4. SEMINARS, SYMPOSIUMS, WORKSHOPS FORUMS 137
19.5. JOURNALS 137
19.6. ACADEMIC WEB RESOURCES 137
20. LITERATURE –PRIMALITY 138
20.1. BOOKS (BK) 138
20.2. LECTURE SCRIPTS 138
20.3. THESES FOR POSTDOC, PHD, MASTER AND BACHELOR DEGREES (PDT, DT,MT,BT) 138
20.3.1. BT- Bachelor Thesis 138
20.3.2. MT – Master Thesis 138
20.3.3. ST - Senior Thesis 138
20.4. GENERAL PAPER (GP) 138
20.5. COLLECTIONS OF PAPERS 138
20.6. PRESENTATIONS/SLIDES AT SEMINARS 138
20.7. OTHER PAPERS 138
20.8. PROPOSALS / SUGGESTIONS 139
21. LITERATURE – OTHER RELATED 139
21.1. ALGEBRA 139
21.2. NUMBER THEORY 139
21.3. COMPUTER COMPLEXITY 139
21.4. COMPLEX ANALYSIS / FUNCTIONS 139
21.5. Cryptography 139
22. APPENDICES 139
22.1. CHARTS 140
22.2. TABLES 140
22.3. DATABASES 140
22.4. MULTIMEDIA DATA 140
22.5. COMPUTATION CODES 140
22.6. WEBSITE FOR THIS THESIS 140