Πώς να εκτελέσετε το τεστ Fermat για πρωταρχικότητα σε λιγότερο από 3 λεπτά

Το τεστ Fermat βασίζεται σε ένα αποτέλεσμα από τη θεωρία αριθμών γνωστή ως το μικρό θεώρημα του Fermat.

Σύμφωνα με το μικρό θεώρημα του Fermat, εάν το n είναι ένας πρωταρχικός αριθμός και το d είναι οποιοσδήποτε θετικός ακέραιος μικρότερος από το n , τότε το d που αυξάνεται στην nth ισχύς είναι σύμφωνο με το d modulo n .

Εάν δύο αριθμοί έχουν το ίδιο υπόλοιπο όταν διαιρούνται με το n τότε λέγεται ότι είναι σύμφωνοι modulo n . d modulo n είναι απλώς το υπόλοιπο ενός αριθμού d όταν διαιρείται με το n .

Για παράδειγμα, το 34 είναι σύμφωνο με το 16 (modulo 3) ως

34 modulo 3 = 1 και 16 modulo 3 = 1.

Τεστ Fermat για πρωτογονικότητα

  1. Για έναν δεδομένο αριθμό n , επιλέξτε έναν τυχαίο θετικό αριθμό d έτσι ώστε d < ; ν.
  2. Υπολογισμός (d ^ n) modulo n .
  3. d modulo n πάντοτε θα είναι d, όπως πάντα επιλέγουμε d που ικανοποιεί την προϋπόθεση d < ; ν.
  4. Εάν το αποτέλεσμα του (d ^ n) modulo n δεν είναι ίσο με το d , τότε το d σίγουρα δεν είναι πρωταρχικό.
  5. Εάν το αποτέλεσμα του (d ^ n) modulo n είναι ίσο με το d , τότε οι πιθανότητες είναι καλές ότι το n είναι prime.
  6. Επιλέξτε ένα άλλο τυχαίο d που ικανοποιεί την κατάσταση d < n και επαναλάβετε τα παραπάνω βήματα.

Σημείωση : Τα παραδείγματα σε αυτήν την ανάρτηση χρησιμοποιούν το Swift 4.1

Χρειαζόμαστε μια συνάρτηση για τον υπολογισμό του εκθετικού αριθμού modulo άλλου αριθμού.

Χρησιμοποιούμε αρθρωτή εκτόνωση για να υπολογίσουμε τιμές όταν ο εκθέτης είναι μεγαλύτερος από 1 καθώς αυτό μας επιτρέπει να εκτελούμε υπολογισμούς ενώ ασχολούμαστε μόνο με αριθμούς μικρότερους από n ( modulo στην παραπάνω συνάρτηση).

Η δοκιμή Fermat επιλέγει τυχαία έναν αριθμό d μεταξύ 1 και n-1 ( αριθμός - 1 στην παραπάνω συνάρτηση). Ο στόχος είναι να ελεγχθεί αν το υπόλοιπο modulo n της nth ισχύος του d είναι ίσο με d.

Η δοκιμή Fermat εκτελείται για τον καθορισμένο αριθμό. Εάν ένας αριθμός αποτύχει στο τεστ Fermat, είμαστε σίγουροι ότι δεν είναι πρώτος. Εάν ένας αριθμός περάσει το τεστ Fermat, δεν είναι εγγυημένο ότι θα είναι πρώτος. Προσπαθούμε να μειώσουμε την πιθανότητα σφάλματος στη δοκιμασία πρωτογενούς λειτουργίας εκτελώντας τη δοκιμή αρκετές φορές.

Προσπαθώντας όλο και περισσότερες τιμές d (ένας τυχαίος θετικός αριθμός μεταξύ 1 και n-1), μπορούμε να αυξήσουμε την εμπιστοσύνη μας στο αποτέλεσμα.