Adobe PDF
(1.28 MB)
| Title Details: | |
|
Factorization & Discrete logarithm |
|
| Authors: |
Draziotis, Konstantinos |
| Description: | |
| Abstract: |
Σε αυτό το κεφάλαιο παρουσιάζουμε αλγορίθμους παραγοντοποίησης και εύρεσης διακριτού λογάριθμου. ΄Οσον αφορά την παραγοντοποίηση, ξεκινάμε με τον απλό αλγόριθμο της δοκιμαστικής διαίρεσης (trial division), συνεχίζουμε με τον αλγόριθμο παραγοντοποίησης του Fermat όπου θέτουμε τις βάσεις για τον υποεκθετικό αλγόριθμο Quadratic Sieve. Αναλύουμε εκτενώς τον αλγόριθμο αυτόν, διότι είναι αρκετά σημαντικός μέχρι σήμερα. Είναι ο καλύτερος αλγόριθμος παραγοντοποίησης για ακεραίους από 50 μέχρι 100 δεκαδικά ψηφία. Επίσης, είναι απλούστερος από τον Number field sieve που είναι ο καλύτερος αλγόριθμος παραγοντοποίησης που έχουμε μέχρι σήμερα. ΄Οσον αφορά τον διακριτό λογάριθμο, παρουσιάζουμε τον αλγόριθμο του Shanks και τον Polard-ρ. Ο δεύτερος αποτελεί μια βελτίωση του πρώτου όσον αφορά τη μνήμη. Επίσης, στην παρουσίαση του αλγορίθμου του Pollard στην άσκηση 10.21 δίνουμε και την παραλλαγή του αλγορίθμου για παραγοντοποίηση.
|
| Linguistic Editors: |
Triantafyllidou, Georgia |
| Technical Editors: |
Draziotis, Konstantinos |
| Graphic Editors: |
Draziotis, Konstantinos |
| Type: |
Chapter |
| Creation Date: | 16-03-2022 |
| Item Details: | |
| License: |
Attribution - NonCommercial - ShareAlike 4.0 International (CC BY-NC-SA 4.0) |
| Handle | http://hdl.handle.net/11419/8191 |
| Bibliographic Reference: | Draziotis, K. (2022). Factorization & Discrete logarithm [Chapter]. In Draziotis, K. 2022. Introduction to Cryptography [Undergraduate textbook]. Kallipos, Open Academic Editions. https://hdl.handle.net/11419/8191 |
| Language: |
Greek |
| Is Part of: |
Introduction to Cryptography |
| Publication Origin: |
Kallipos, Open Academic Editions |