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: 2022
Item Details:
License: Attribution - NonCommercial - ShareAlike 4.0 International (CC BY-NC-SA 4.0)
Handle http://hdl.handle.net/11419/8191
Bibliographic Citation: Draziotis, K. (2022). Factorization & Discrete logarithm [Chapter]. In Draziotis, K. 2022. Introduction to Cryptography [Undergraduate textbook]. Kallipos, Open Academic Editions. chapter 10. http://hdl.handle.net/11419/8191
Language: Greek
Is Part of: Introduction to Cryptography
Publication Origin: Kallipos, Open Academic Editions