Υπολογιστής Παραγοντοποίησης Fermat

Σχετικά με αυτόν τον υπολογιστή

Η μέθοδος παραγοντοποίησης του Fermat εκμεταλλεύεται το γεγονός ότι κάθε περιττός ακέραιος N μπορεί να γραφτεί ως διαφορά δύο τετραγώνων, N = a² − b² = (a−b)(a+b). Ο αλγόριθμος ξεκινά από a = ⌈√N⌉ και αυξάνει το a κατά 1 σε κάθε βήμα, ελέγχοντας αν το a² − N είναι το ίδιο τέλειο τετράγωνο (b²)· τη στιγμή που είναι, το N παραγοντοποιείται αμέσως σε (a−b)(a+b). Αυτός ο υπολογιστής εκτελεί αυτόν τον βρόχο και δείχνει κάθε βήμα που έκανε για να βρει τους παράγοντες.

Η μέθοδος συγκλίνει σε πολύ λίγα βήματα όταν οι δύο παράγοντες του N είναι κοντά μεταξύ τους — η κύρια αδυναμία της είναι και η σημαντικότερη πραγματική της χρήση: οι φοιτητές κρυπτογραφίας και οι ερευνητές ασφάλειας χρησιμοποιούν την παραγοντοποίηση Fermat για να δείξουν γιατί τα moduli του RSA πρέπει να κατασκευάζονται από πρώτους αριθμούς που απέχουν πολύ μεταξύ τους, αφού πρώτοι που επιλέγονται πολύ κοντά κάνουν το modulus ασήμαντα εύκολο να σπάσει. Αποτελεί επίσης τυπική άσκηση στα μαθήματα θεωρίας αριθμών για την επίδειξη του συλλογισμού της διαφοράς τετραγώνων.