Study started since 2011年10月17日 素性测试算法,素性测定(11Y11) primality testing



Yüklə 1,18 Mb.
səhifə1/13
tarix22.07.2018
ölçüsü1,18 Mb.
#58231
  1   2   3   4   5   6   7   8   9   ...   13

Study started since 2011年10月17日


素性测试算法,素性测定(11Y11) primality testing

Bachelor semester project Randomized and Deterministic Primality Testing.pdf 10





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




Yüklə 1,18 Mb.

Dostları ilə paylaş:
  1   2   3   4   5   6   7   8   9   ...   13




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə