Πιστοποίηση Πρώτου

Primality Testing (Αγγλική)

  1. MSc thesis
  2. Αμπατζή, Αναστασία
  3. Μεταπτυχιακές Σπουδές στα Μαθηματικά (ΜΣΜ)
  4. 30 Σεπτεμβρίου 2018 [2018-09-30]
  5. Ελληνικά
  6. 87
  7. Πουλάκης, Δημήτριος
  8. Πιθανοτικά Κριτήρια Πιστοποίησης Πρώτου | Πιστοποίηση Πρώτου | Κριτήριο Miller - Rabin | Κριτήριο Solovay - Strassen | Probabilistic tests | Primality testing | Miller - Rabin primality test | Solovay - Strassen primality test
  9. 5
  10. 41
  11. Περιέχει : πίνακες, σχήματα, εικόνες
    • Η δημιουργία των αριθμών προέρχεται από την ανάγκη του ανθρώπου να εξηγήσει τον κόσμο που τον περιβάλλει. Οι μαθηματικοί παρατήρησαν, ότι όλοι οι αριθμοί δεν έχουν τις ίδιες ιδιότητες μεταξύ τους. Έτσι κατασκεύασαν κατηγορίες και τους ταξινόμησαν ανάλογα. Ένας τρόπος διαχωρισμού ήταν σε πρώτους και σύνθετους αριθμούς. Πρώτοι αριθμοί είναι αυτοί που δεν διαιρούνται από κανέναν άλλον αριθμό εκτός από τον εαυτό τους και τη μονάδα. Ενώ σύνθετοι ονομάζονται οι αριθμοί που δεν είναι πρώτοι. Οι πρώτοι αριθμοί, αν και είχαν οριστεί τόσα χρόνια πριν, δεν είχαν αρχικά κάποια πρακτική χρησιμότητα παρά μόνο θεωρητικό ενδιαφέρον. Αυτό όμως άλλαξε τον 19ο αιώνα. Τότε, εξαιτίας των πολέμων υπήρχε μια ανάγκη για μυστικότητα και κώδικες οι οποίοι δεν μπορούσαν να κατανοηθούν από όλους. Συνεπώς παρατηρήθηκε ότι ένας κώδικας που χρησιμοποιεί το γινόμενο δύο πρώτων αριθμών είναι πιο δύσκολο να "σπάσει", γιατί έχει μόνο τέσσερις παράγοντες. Αργότερα μάλιστα, όταν άρχισε η ανάπτυξη των ηλεκτρονικών υπολογιστών, η ανάγκη για ασφαλείς συναλλαγές ήταν πιο απαραίτητη από ποτέ άλλοτε. Αυτό είχε σαν αποτέλεσμα την ανάπτυξη της Κρυπτογραφίας και του RSA. Το RSA είναι ένας κρυπταλγόριθμος ασύμμετρου κλειδιού που χρησιμοποιεί δύο κλειδιά, ένα δημόσιο για τη διάρκεια της κρυπτογράφησης και ένα ιδιωτικό για την αποκρυπτογράφηση. Οι πρώτοι αριθμοί χρησιμοποιούνται στην ανάπτυξη του δημοσίου κλειδιού. Σ' αυτό το σημείο δημιουργείται η ανάγκη ανάπτυξης μεθόδων που να ελέγχουν αν ένας αριθμός είναι πρώτος ή σύνθετος. Στα πλαίσια της παρούσας διπλωματικής εργασίας θα παρουσιαστούν τέτοιες μέθοδοι. Συγκεκριμένα, υπάρχουν κριτήρια, τα οποία μπορούν να καταδείξουν με σιγουριά αν ένας αριθμός είναι ή δεν είναι πρώτος και ονομάζονται αιτιοκρατικά κριτήρια πιστοποίησης πρώτου. Ακόμα υπάρχουν κριτήρια που χρησιμοποιούν μια τυχαία επιλογή ενός αριθμού, ο οποίος έχει την ικανότητα να επηρεάσει το αποτέλεσμα, αυτά ονομάζονται πιθανοτικά κριτήρια. Σε αυτή την εργασία θα μελετηθούν τέτοια πιθανοτικά κριτήρια. Η εργασία ξεκινά με μια μικρή εισαγωγή, όπου αναφέρονται μερικά σημαντικά πρόσωπα, που βοήθησαν στην ανάπτυξη μεθόδων πιστοποίησης πρώτων. Στη συνέχεια, στο 1ο κεφάλαιο, παρουσιάζονται έννοιες από τη θεωρία αριθμών που είναι απαραίτητες για την κατανόηση των εννοιών που υπάρχουν στα κεφάλαια που ακολουθούν. Στο 2ο κεφάλαιο παρουσιάζονται κάποια κλασικά κριτήρια πιστοποίησης πρώτων. Αυτά τα κριτήρια αποτέλεσαν βάσεις για την ανάπτυξη των σύγχρονων μεθόδων που χρησιμοποιούνται σήμερα. Δεν θα μπορούσε να παραλειφθεί η αναφορά στους ψευδοπρώτους αριθμούς, η οποία γίνεται στο 3ο κεφάλαιο. Οι αριθμοί αυτοί φαίνονται εκ πρώτης όψεως να είναι πρώτοι, ενώ στην πραγματικότητα είναι σύνθετοι. Στα κεφάλαια 4 και 5 γίνεται αναλυτική περιγραφή των κριτηρίων Solovay - Strassen και Miller - Rabin αντίστοιχα. Τα κριτήρια αυτά είναι τα σημαντικότερα πιθανοτικά κριτήρια. Τέλος στο κεφάλαιο 6, παρουσιάζονται στα κριτήρια Quadratic Frobenius και Baillie - PSW.
    • Humans invented numbers in an effort to explain the world that surrounds them. The mathematicians noticed that do not all numbers have the same properties. So, they formed categories and classified the numbers accordingly. One way of categorization was in prime and composites numbers. A prime number is a natural number that has no integer factors except one and itself. On the other hand, a number that is not prime is called composite. The prime numbers, although they were defined many years ago, were for a long time of no specific use, rather than of merely academic interest. That changed however in the 19th century. Because of the wars, there was then a need for secrecy and for the development of codes that were not to be easily understood by anybody. Under those circumstances it was noticed, that a code which uses the product of two prime numbers is more difficult to crack, because it has only four factors. Later on, when the rapid development of computers began, was the need for secure transactions more necessary than ever before. This resulted in the development of Cryptography and RSA. RSA describes an asymmetric cryptosystem that uses one public keys for the duration of encryption and one private key for the decryption. Prime numbers are used in the development of the public key. Therefore, tests are needed, in order to establish, whether a number is prime or not. In the course of this paper such tests are to be presented. There are tests, that can decide with certainty, if a number is prime or not and those are called \enquote{deterministic test for primality testing}. Moreover, there are algorithms to be found, that use a random number, which affects the final result. Those algorithms are \enquote{the probabilistic tests for primality testing}. In this paper, are probabilistic tests to be studied. The paper begins with a brief introduction listing some important mathematicians who helped develop primality testing. In chapter 1 are theorems from number theory presented, that are necessary for understanding the concepts of the following chapters. In chapter 2 are some classical theorems of primality testing presented. Those theorems are the basis for the development of the modern theorems, which are used today. Chapter 3 is dedicated to pseudoprimes. Those are numbers that appear to be primes, but actually are composites. In chapters 4 and 5 are respectively the Solovay – Strassen primality test and the Miller – Rabin primality test presented. Those tests are the most important of the probabilistic testing. The paper closes with chapter 6, where the Quadratic Frobenius Testing and the Baillie – PSW testing are presented.
  13. Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.