Περιεχόμενο

• Βήματα
• Μέρος 1 από 3: Δοκιμές απλότητας
• Μέρος 2 από 3: Πώς λειτουργούν οι δοκιμές απλότητας
• Μέρος 3 από 3: Χρησιμοποιώντας το κινέζικο θεώρημα υπολειμμάτων
• Συμβουλές
• Τι χρειάζεσαι

Οι πρώτοι αριθμοί είναι αριθμοί που διαιρούνται μόνο με τον εαυτό τους και με το 1. Όλοι οι άλλοι αριθμοί ονομάζονται σύνθετοι αριθμοί. Υπάρχουν πολλοί τρόποι για να προσδιορίσετε εάν ένας αριθμός είναι πρώτος και όλοι έχουν τα δικά τους πλεονεκτήματα και μειονεκτήματα. Από τη μία πλευρά, μερικές από τις μεθόδους είναι πολύ ακριβείς, αλλά είναι αρκετά περίπλοκες εάν ασχολείστε με μεγάλους αριθμούς. Από την άλλη πλευρά, υπάρχουν πολύ πιο γρήγοροι τρόποι, αλλά μπορούν να οδηγήσουν σε λανθασμένα αποτελέσματα. Η επιλογή της κατάλληλης μεθόδου εξαρτάται από το πόσο μεγάλοι είναι οι αριθμοί με τους οποίους εργάζεστε.

Βήματα

Μέρος 1 από 3: Δοκιμές απλότητας

Σημείωση: σε όλους τους τύπους ν δηλώνει τον αριθμό που πρέπει να ελεγχθεί.

1. 1 Απαρίθμηση διαιρετών. Αρκεί να διαιρέσουμε ν σε όλους τους πρώτους αριθμούς από το 2 στη στρογγυλεμένη τιμή (${ displaystyle { sqrt {n}}}$).
2. 2 Το μικρό θεώρημα του Φερμά. Προειδοποίηση: μερικές φορές η δοκιμή εντοπίζει ψευδώς τους σύνθετους αριθμούς ως πρώτους, ακόμη και για όλες τις τιμές του α.
   • Ας επιλέξουμε έναν ακέραιο ένατέτοια ώστε 2 ≤ a ≤ n - 1.
   • Εάν a (mod n) = a (mod n) τότε ο αριθμός είναι πιθανώς πρώτος. Εάν η ισότητα δεν ικανοποιείται, ο αριθμός n είναι σύνθετος.
   • Ελέγξτε τη δεδομένη ισότητα για πολλαπλές τιμές έναγια να αυξηθεί η πιθανότητα ο αριθμός που δοκιμάζεται να είναι όντως πρώτος.
3. 3 Δοκιμή Miller-Rabin. Προειδοποίηση: μερικές φορές, αν και σπάνια, για πολλαπλές τιμές a, η δοκιμή εντοπίζει εσφαλμένα τους σύνθετους αριθμούς ως πρώτους.
   • Βρείτε τις ποσότητες s και d τέτοια ώστε ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Επιλέξτε έναν ακέραιο ένα στο εύρος 2 ≤ a ≤ n - 1.
   • Εάν a = +1 (mod n) ή -1 (mod n), τότε το n είναι πιθανώς πρώτο. Σε αυτήν την περίπτωση, μεταβείτε στο αποτέλεσμα της δοκιμής. Εάν η ισότητα δεν ισχύει, προχωρήστε στο επόμενο βήμα.
   • Τετραγωνίστε την απάντησή σας (${ displaystyle a ^ {2d}}$). Εάν λάβετε -1 (mod n), τότε το n είναι πιθανώς ένας πρώτος αριθμός. Σε αυτήν την περίπτωση, μεταβείτε στο αποτέλεσμα της δοκιμής. Εάν η ισότητα αποτύχει, επαναλάβετε (${ displaystyle a ^ {4d}}$ και ούτω καθεξής) μέχρι ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • Εάν σε κάποιο βήμα μετά τον τετραγωνισμό ενός αριθμού διαφορετικού από ${ displaystyle pm 1}$ (mod n), έχετε +1 (mod n), οπότε το n είναι ένας σύνθετος αριθμός. Αν ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), τότε το n δεν είναι πρώτο.
   • Αποτέλεσμα δοκιμής: εάν το n περάσει τη δοκιμή, επαναλάβετε το για άλλες τιμές ένανα αυξήσει την εμπιστοσύνη.

Μέρος 2 από 3: Πώς λειτουργούν οι δοκιμές απλότητας

1. 1 Απαρίθμηση διαιρετών. Εξ ορισμού, ο αριθμός ν είναι απλή μόνο αν δεν διαιρείται με 2 και άλλους ακέραιους αριθμούς εκτός από το 1 και τον εαυτό του. Ο παραπάνω τύπος σάς επιτρέπει να αφαιρέσετε περιττά βήματα και να εξοικονομήσετε χρόνο: για παράδειγμα, αφού ελέγξετε εάν ένας αριθμός διαιρείται με το 3, δεν χρειάζεται να ελέγξετε αν διαιρείται με το 9.
   • Η συνάρτηση δαπέδου (x) στρογγυλοποιεί το x στον πλησιέστερο ακέραιο μικρότερο ή ίσο με το x.
2. 2 Μάθετε για την αρθρωτή αριθμητική. Η λειτουργία "x mod y" (το mod είναι συντομογραφία της λατινικής λέξης "modulo", δηλαδή "module") σημαίνει "διαιρέστε το x με το y και βρείτε το υπόλοιπο". Με άλλα λόγια, στην αρθρωτή αριθμητική, με την επίτευξη μιας συγκεκριμένης τιμής, η οποία ονομάζεται μονάδα μέτρησης, οι αριθμοί "γυρίζουν" ξανά στο μηδέν. Για παράδειγμα, το ρολόι μετρά αντίστροφα με την ενότητα 12: δείχνει 10, 11 και 12 ώρες και μετά επιστρέφει στο 1.
   • Πολλοί αριθμομηχανές διαθέτουν κλειδί mod. Το τέλος αυτής της ενότητας σας δείχνει πώς να υπολογίσετε με μη αυτόματο τρόπο αυτήν τη συνάρτηση για μεγάλους αριθμούς.
3. 3 Μάθετε για τις παγίδες του Μικρού Θεωρήματος του Fermat. Όλοι οι αριθμοί για τους οποίους δεν πληρούνται οι προϋποθέσεις δοκιμής είναι σύνθετοι, αλλά οι υπόλοιποι αριθμοί είναι μόνο πιθανώς είναι απλά. Αν θέλετε να αποφύγετε εσφαλμένα αποτελέσματα, αναζητήστε ν στη λίστα των "αριθμών Carmichael" (σύνθετοι αριθμοί που ικανοποιούν αυτή τη δοκιμή) και "αριθμοί ψευδοπυρήνων Fermat" (αυτοί οι αριθμοί πληρούν τις προϋποθέσεις δοκιμής μόνο για ορισμένες τιμές ένα).
4. 4 Εάν είναι βολικό, χρησιμοποιήστε τη δοκιμή Miller-Rabin. Αν και αυτή η μέθοδος είναι μάλλον δυσκίνητη για χειροκίνητους υπολογισμούς, χρησιμοποιείται συχνά σε προγράμματα υπολογιστών. Παρέχει αποδεκτή ταχύτητα και λιγότερα λάθη από τη μέθοδο του Fermat. Ένας σύνθετος αριθμός δεν θα ληφθεί ως πρώτος αριθμός εάν εκτελούνται υπολογισμοί για περισσότερες από ¼ τιμές ένα... Εάν επιλέξετε τυχαία διαφορετικές τιμές ένα και για όλους αυτούς η δοκιμή θα δώσει θετικό αποτέλεσμα, μπορούμε να υποθέσουμε με αρκετά υψηλό βαθμό εμπιστοσύνης ότι ν είναι πρώτος αριθμός.
5. 5 Για μεγάλους αριθμούς, χρησιμοποιήστε αριθμητική αριθμητική. Εάν δεν έχετε στη διάθεσή σας μια αριθμομηχανή mod ή η αριθμομηχανή δεν έχει σχεδιαστεί για να χειρίζεται τόσο μεγάλους αριθμούς, χρησιμοποιήστε ιδιότητες ισχύος και αρθρωτή αριθμητική για να διευκολύνετε τους υπολογισμούς. Παρακάτω είναι ένα παράδειγμα για ${ displaystyle 3 ^ {50}}$ mod 50:
   • Ξαναγράψτε την έκφραση σε πιο βολική μορφή: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Οι μη αυτόματοι υπολογισμοί ενδέχεται να απαιτούν περαιτέρω απλουστεύσεις.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Εδώ λάβαμε υπόψη την ιδιότητα του αρθρωτού πολλαπλασιασμού.
   • ${ displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ displaystyle (3 ^ {25}}$ mod 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ displaystyle (43 * 43)}$ mod 50.
   • ${ displaystyle = 1849}$ mod 50.
   • ${ displaystyle = 49}$.

Μέρος 3 από 3: Χρησιμοποιώντας το κινέζικο θεώρημα υπολειμμάτων

1. 1 Επιλέξτε δύο αριθμούς. Ένας από τους αριθμούς πρέπει να είναι σύνθετος και ο άλλος πρέπει να είναι ακριβώς αυτός που θέλετε να δοκιμάσετε για απλότητα.
   • Αριθμός1 = 35
   • Αριθμός2 = 97
2. 2 Επιλέξτε δύο τιμές μεγαλύτερες από μηδέν και, αντίστοιχα, μικρότερες από τους αριθμούς Number1 και Number2. Αυτές οι τιμές δεν πρέπει να είναι ίδιες.
   • Τιμή 1 = 1
   • Τιμή2 = 2
3. 3 Υπολογίστε το MMI (Μαθηματικό πολλαπλασιαστικό αντίστροφο) για τον αριθμό 1 και τον αριθμό 2.
   • Υπολογίστε MMI
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • Μόνο για πρώτους αριθμούς (αυτό θα δώσει έναν αριθμό για σύνθετους αριθμούς, αλλά δεν θα είναι το MMI του):
     • MMI1 = (Number2 ^ (Number1-2))% Number1
     • MMI2 = (Number1 ^ (Number2-2))% Number2
   • Για παράδειγμα:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Δημιουργήστε έναν πίνακα για κάθε MMI κάτω από τις ενότητες log2:
   • Για MMI1
     • F (1) = Αριθμός2% Αριθμός1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Number1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Αριθμός1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Αριθμός1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Αριθμός1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Αριθμός1 = 1 * 1% 35 = 1
   • Υπολογίστε ζευγαρωμένους αριθμούς 1 - 2
     • 35 -2 = 33 (10001) βάση 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Για MMI2
     • F (1) = Αριθμός1% Αριθμός2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Number2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Number2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Αριθμός2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Αριθμός2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Number2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Number2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Number2 = 35 * 35 mod 97 = 61
   • Υπολογίστε το ζευγαρωμένο αριθμό 2 - 2
     • 97 - 2 = 95 = (1011111) βάση 2
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = ((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Υπολογισμός (Τιμή1 * Αριθμός2 * MMI1 + Τιμή2 * Αριθμός1 * MMI2)% (Αριθμός1 * Αριθμός2)
   • Απάντηση = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Απάντηση = (2619 + 4270)% 3395
   • Απάντηση = 99
6. 6 Βεβαιωθείτε ότι ο αριθμός 1 δεν είναι πρώτος
   • Υπολογισμός (Απάντηση - Τιμή 1)% Αριθμός 1
   • 99 – 1 % 35 = 28
   • Δεδομένου ότι το 28 είναι μεγαλύτερο από 0, το 35 δεν είναι πρώτος αριθμός.
7. 7 Ελέγξτε ότι ο αριθμός 2 είναι πρώτος.
   • Υπολογισμός (Απάντηση - Τιμή2)% Αριθμός2
   • 99 – 2 % 97 = 0
   • Δεδομένου ότι το 0 είναι 0, το 97 είναι πιθανότατα ένας πρώτος αριθμός.
8. 8 Επαναλάβετε τα βήματα 1 έως 7 τουλάχιστον δύο ακόμη φορές.
   • Εάν λάβετε 0 στο βήμα 7:
     • Χρησιμοποιήστε διαφορετικό Number1 εάν ο Number1 δεν είναι πρώτος.
     • Χρησιμοποιήστε έναν άλλο Αριθμό 1 εάν ο Αριθμός 1 είναι πρώτος. Σε αυτήν την περίπτωση, θα πρέπει να λάβετε 0 στα βήματα 6 και 7.
     • Χρησιμοποιήστε διαφορετική έννοια1 και έννοια2.
   • Εάν στο βήμα 7 παίρνετε σταθερά 0, τότε ο αριθμός 2 είναι πολύ πιθανό να είναι πρώτος.
   • Τα βήματα 1 έως 7 μπορεί να οδηγήσουν σε σφάλμα εάν ο αριθμός 1 δεν είναι πρώτος και ο αριθμός 2 διαιρείται στον αριθμό 1. Η περιγραφόμενη μέθοδος λειτουργεί σε όλες τις περιπτώσεις όταν και οι δύο αριθμοί είναι πρώτοι.
   • Ο λόγος που πρέπει να επαναλάβετε τα βήματα 1 έως 7 είναι επειδή σε ορισμένες περιπτώσεις, ακόμη και αν ο αριθμός 1 και ο αριθμός 2 δεν είναι πρώτοι, στο βήμα 7 θα λάβετε 0 (για έναν ή και τους δύο αριθμούς). Αυτό συμβαίνει σπάνια.Επιλέξτε έναν άλλο Αριθμό 1 (σύνθετο) και εάν ο Αριθμός 2 δεν είναι πρώτος, τότε ο Αριθμός 2 δεν θα ισούται με μηδέν στο βήμα 7 (εκτός από την περίπτωση που ο Αριθμός 1 είναι διαιρέτης του Αριθμού 2 - εδώ οι πρώτοι θα είναι πάντα μηδενικοί στο βήμα 7).

Συμβουλές

• Πρώτοι αριθμοί από 168 έως 1000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Παρόλο που η δοκιμή ωμής δύναμης είναι μια κουραστική δοκιμή όταν εργάζεστε με μεγάλους αριθμούς, είναι αρκετά αποτελεσματική για μικρούς αριθμούς. Ακόμη και στην περίπτωση μεγάλων αριθμών, ξεκινήστε δοκιμάζοντας μικρούς διαιρέτες και, στη συνέχεια, προχωρήστε σε πιο εξελιγμένες μεθόδους για τον έλεγχο της απλότητας των αριθμών (εάν δεν βρεθούν μικροί διαιρέτες).

Τι χρειάζεσαι

• Χαρτί, στυλό ή υπολογιστή