Quadratic residues and continued fractions

Quadratic residues and continued fractions

URI: https://www.openarchives.gr/aggregator-openarchives/edm/ntua/000011-123456789_5380
RDF/XML JSON-LD

This item is provided by the institution :
National Technical University of Athens

Repository :
Digital Library of National Technical University of Athens | Dspace@NTUA

see the original item page
in the repository's web site and access all digital files if the item^*

Title

Τετραγωνικά υπόλοιπα και συνεχή κλάσματα (EL)

Quadratic residues and continued fractions (EN)

Creator

Μάστακας, Κωνσταντίνος Α. (EL)

Mastakas, Konstantinos A. (EN)

Contributor

Κουκουβίνος, Χρήστος (EL)

Στεφανέας, Πέτρος (EL)

Παπαϊωάννου, Αλέξανδρος (EL)

Type

bachelorThesis

Thesis
Bachelor thesis (EN)

Issued

2011-11-18T11:31:21Z

2011-10-31

2011-11-07

2011-11-18

Year

2011 (EN)

Description

Η διπλωματική μου εργασία έχει σαν στόχο την μελέτη και ανάλυση της θεωρίας των “Τετραγωνικών Υπολοίπων” και των “Συνεχών Κλασμάτων”, δύο πολύ βασικών κλάδων της θεωρίας αριθμών, που έχουν εφαρμογή στην Κρυπτογραφία. Στο πρώτο κεφάλαιο γίνεται μια εισαγωγή στην θεωρία αριθμών. Μελετάται η έννοια της διαιρετότητας, αποδεικνύεται η απειρία των πρώτων και το θεμελιώδες θεώρημα της αριθμητικής. Ακόμα, ορίζεται η ισοδυναμία μεταξύ δύο αριθμών και στο τέλος του κεφαλαίου αποδεικνύονται τα θεωρήματα Euler και Fermat. Στο δεύτερο κεφάλαιο μελετάμε τα τετραγωνικά υπόλοιπα ενός αριθμού. Στην αρχή αποδεικνύουμε ιδιότητες των τετραγωνικών υπολοίπων περιττών πρώτων, εισάγουμε το σύμβολο του Legendre και διατυπώνουμε το κριτήριο Euler. Στην συνέχεια αποδεικνύουμε ένα από τα πιο βασικά θεωρήματα στην θεωρία αριθμών, τον “Νόμο της τετραγωνικής αντιστροφής”. Τελειώνοντας το κεφάλαιο επεκτείνουμε το σύμβολο Legendre στο σύμβολο Jacobi και κλείνουμε το κεφάλαιο με έναν αλγόριθμο που υπολογίζει το σύμβολο Jacobi. Στο τρίτο κεφάλαιο ενδιαφερόμαστε να βρούμε με αποδοτικό τρόπο τις τετραγωνικές ρίζες των τετραγωνικών υπολοίπων. Παραθέτουμε τους κλειστούς τύπους που υπάρχουν για τους πρώτους που αφήνουν υπόλοιπο 3 και 5 στην διαίρεση με το 4 και το 8 αντίστοιχα. Έπειτα παραθέτουμε τον αλγόριθμο των Tonelli και Shanks και τέλος αναπτύσουμε τον αλγόριθμο του Cornacchia. Στο τέταρτο και τελευταίο κεφάλαιο κάνουμε μια εισαγωγή στα συνεχή κλάσματα. Στην αρχή τα ορίζουμε και μελετάμε τις ιδιότητες των συγκλίνοντών τους. Ύστερα δείχνουμε ότι κάθε πραγματικός αριθμός μπορεί να αναπαρασταθεί μοναδικά από ένα συνεχές κλάσμα και κλείνουμε το κεφάλαιο αποδεικνύοντας ότι τα συνεχή κλάσματα αποτελούν την καλύτερη προσέγγιση ενός πραγματικού αριθμού. (EL)

69 σ. (EL)

Κωνσταντίνος Α. Μάστακας (EL)

Scientific field

Natural Sciences
Mathematics (EN)

Subject

Θεωρία αριθμών (EL)

Τετραγωνικά υπόλοιπα (EL)

Σύμβολο Legendre (EL)

Πρώτοι αριθμοί (EL)

Τετραγωνικές ρίζες (EL)

Συνεχή κλάσματα (EL)

Prime numbers (EN)