Η σύντομη απάντηση
Η παραγοντοποίηση του πρώτου αριθμού διασπά έναν αριθμό στους πρώτους αριθμούς που πολλαπλασιάζονται μαζί για να τον κάνουν. 60 = 2² × 3 × 5 — κανένας άλλος συνδυασμός πρώτων δεν λειτουργεί, επειδή κάθε ακέραιος αριθμός μεγαλύτερος από 1 έχει ακριβώς έναν πρώτο παραγοντοποίηση (το Θεμελιώδες Θεώρημα της Αριθμητικής). Βρείτε το διαιρώντας επανειλημμένα με τον μικρότερο πρώτο που ταιριάζει, μεταβαίνοντας στον επόμενο πρώτο μόλις σταματήσει να διαιρείται ομοιόμορφα.
Βασικά φαγητά
- Κάθε ακέραιος αριθμός μεγαλύτερος από 1 έχει ακριβώς έναν πρώτο παραγοντοποίηση — ανεξάρτητα από ποιους πρώτους δοκιμάζετε πρώτοι, καταλήγετε στο ίδιο αποτέλεσμα.
- Ένας πρώτος αριθμός συντελεστεί σε έναν μόνο όρο: τον εαυτό του στην πρώτη δύναμη (7 = 7¹).
- Είτε το δεκαδικό ενός κλάσματος τερματίζει είτε επαναλαμβάνει τα ίχνη απευθείας πίσω στην παραγοντοποίηση του πρώτου — μόνο 2 και 5 στον παρονομαστή παράγουν ένα τερματικό δεκαδικό.
- Η αρχική παραγοντοποίηση γίνεται εκθετικά πιο δύσκολη για τους υπολογιστές καθώς οι αριθμοί μεγαλώνουν, κάτι που αποτελεί τη βάση για την ασφάλεια της κρυπτογράφησης RSA.
Η μέθοδος διαίρεσης, βήμα προς βήμα
Ξεκινήστε με τον μικρότερο πρώτο πρώτο, 2. Εάν διαιρεί τον αριθμό ομοιόμορφα, διαιρέστε και επαναλάβετε με το 2 ξανά — μην προχωρήσετε στον επόμενο πρώτο έως ότου το 2 δεν λειτουργεί πλέον. Μόλις σταματήσει να διαιρείται ομοιόμορφα, μετακινηθείτε στο 3, μετά στο 5, μετά στο 7 και ούτω καθεξής, δοκιμάζοντας πάντα τον ίδιο πρώτο αριθμό πριν προχωρήσετε. Σταματήστε όταν το πηλίκο τρεξίματος φτάσει στο 1.
Παράδειγμα εργασίας: factoring 360
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45 (2 δεν διαιρείται πλέον ομοιόμορφα — μετακίνηση στο 3)
45 ÷ 3 = 15
15 ÷ 3 = 5 (3 δεν διαιρούνται πλέον ομοιόμορφα — μετακινηθείτε στο 5)
5 ÷ 5 = 1 (ολοκληρώθηκε)
360 = 2³ × 3² × 5
Έλεγχος της απάντησης: 2³ = 8, 3² = 9 και 8 × 9 × 5 = 360 — επιβεβαίωση ότι η παραγοντοποίηση είναι σωστή.
Γιατί η κύρια παραγοντοποίηση εξασφαλίζει την κρυπτογράφηση
Για μικρούς αριθμούς, η παραγοντοποίηση είναι σχεδόν στιγμιαία — ένας υπολογιστής συντελεστή 91 σε 7 × 13 σε ένα κλάσμα του δευτερολέπτου. Αλλά όταν οι δύο πρώτοι που εμπλέκονται έχουν εκατοντάδες ψηφία, ο πολλαπλασιασμός τους μαζί (για τη δημιουργία ενός δημόσιου κλειδιού) διαρκεί ακόμα χιλιοστά του δευτερολέπτου, ενώ η διάσπαση αυτού του προϊόντος (σπάσιμο του κλειδιού) θα διαρκούσε περισσότερο από την ηλικία του σύμπαντος χρησιμοποιώντας κλασικούς υπολογιστές. Το RSA και παρόμοια κρυπτογραφικά συστήματα χτίζουν ολόκληρο το μοντέλο ασφαλείας τους σε αυτήν την πρακτική δυσκολία μιας κατεύθυνσης.
Συνήθη λάθη που πρέπει να αποφεύγονται
- Διακοπή μετά τη διαίρεση με έναν πρώτο μόνο μία φορά — συνεχίστε να διαιρείτε με τον ίδιο πρώτο αριθμό επανειλημμένα μέχρι να μην διαιρείται πλέον ομοιόμορφα πριν προχωρήσετε.
- Έλεγχος σύνθετων διαιρετών όπως το 4 ή το 6 — μόνο οι πρώτοι διαιρέτες ανήκουν σε μια παραγοντοποίηση πρώτων. Οι κύριοι παράγοντες ενός σύνθετου υλικού θα είχαν ήδη βρεθεί πρώτα.
- Ξεχνώντας να συμπτύξετε τους επαναλαμβανόμενους πρώτους σε εκθέτες — γράψτε το 2 × 2 × 2 × 3 × 3 ως 2³ × 3², όχι ως πέντε ξεχωριστούς επαναλαμβανόμενους όρους.
- Υποθέτοντας ότι κάθε μεγάλος αριθμός είναι δύσκολο να παραμετροποιηθεί — οι αριθμοί με μικρούς πρώτους παράγοντες παράγονται γρήγορα ανεξάρτητα από το μέγεθος. είναι συγκεκριμένα προϊόντα δύο παρόμοιων μεγάλων πρώτων που αντιστέκονται στην παραγοντοποίηση.
Σχετικές αριθμομηχανές
- Υπολογιστής συντελεστών — απαριθμήστε κάθε παράγοντα ενός αριθμού, όχι μόνο τα κύρια δομικά στοιχεία του.
- Ο καλύτερος υπολογιστής κοινού παράγοντα — βάλτε τους κοινούς κύριους παράγοντες να εργαστούν για την εύρεση του GCF.
- Λιγότερο κοινός πολλαπλός υπολογιστής — συνδυάστε τους πρώτους παραγοντοποιήσεις για να βρείτε ένα κοινό πολλαπλάσιο.
- Υπολογιστής μεγάλου αριθμού — χειριστεί τα τεράστια προϊόντα που μπορούν να δημιουργήσουν μεγάλοι κύριοι παράγοντες.