📬 Η πρόκληση
Ο Marin Mersenne έγραψε κάποτε στον Pierre de Fermat ρωτώντας αν ο αριθμός 100.895.598.169 είναι πρώτος. Ο Fermat απάντησε σχεδόν αμέσως ότι δεν είναι — είναι το γινόμενο των αριθμών 898.423 και 112.303, οι οποίοι είναι και οι δύο πρώτοι. Επαληθεύσαμε τον υπολογισμό: είναι απολύτως σωστός.
Το ανέκδοτο συχνά αφηγείται ως ένα άλυτο μυστήριο — πώς μπόρεσε ο Fermat να παραγοντοποιήσει έναν τόσο μεγάλο αριθμό τόσο γρήγορα, χωρίς αριθμομηχανή, τον 17ο αιώνα;
🔓 Το μυστήριο έχει, στην πραγματικότητα, λύση
Παρά τη δημοφιλή αφήγηση ότι «κανείς δεν ξέρει» πώς το έκανε, οι ιστορικοί των μαθηματικών γνωρίζουν πράγματι την απάντηση — και μάλιστα με μεγάλη ακρίβεια: σε επιστολή του προς τον Mersenne, χρονολογημένη στις 7 Απριλίου 1643, ο ίδιος ο Fermat περιέγραψε τη μέθοδο που χρησιμοποίησε, ακριβώς πάνω σε αυτό το παράδειγμα. Είναι η τεχνική που είναι σήμερα γνωστή ως «μέθοδος παραγοντοποίησης του Fermat».
Η ιδέα είναι κομψή: κάθε περιττός αριθμός N μπορεί να γραφτεί ως διαφορά δύο τετραγώνων, N = a² − b² = (a+b)(a−b). Ο Fermat δοκίμαζε διαδοχικές τιμές του a, ξεκινώντας από τη μικρότερη δυνατή (τη στρογγυλοποιημένη προς τα πάνω τετραγωνική ρίζα του N), μέχρι να βρει μια τιμή για την οποία το a² − N να είναι τέλειο τετράγωνο. Η μέθοδος είναι ιδιαίτερα αποδοτική ακριβώς όταν οι δύο ζητούμενοι παράγοντες βρίσκονται σχετικά κοντά ο ένας στον άλλον — κάτι που ίσχυε στην περίπτωση των 898.423 και 112.303.
💡 Μια τεχνική που ζει ακόμη σήμερα
Η μέθοδος του Fermat δεν παρέμεινε απλώς ιστορική περιέργεια. Αποτελεί τη βάση πάνω στην οποία χτίστηκαν πολύ πιο σύγχρονες και ισχυρές τεχνικές παραγοντοποίησης, όπως το quadratic sieve και το general number field sieve — αλγόριθμοι που χρησιμοποιούνται σήμερα στην πράξη για να δοκιμαστεί η ασφάλεια συστημάτων κρυπτογράφησης όπως το RSA, το οποίο βασίζεται ακριβώς στη δυσκολία παραγοντοποίησης πολύ μεγάλων αριθμών.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου