Αριθμομηχανή θεωρίας αριθμών — Πρώτοι, ΜΚΔ/ΕΚΠ, modular αριθμητική & άλλα
Αριθμομηχανή θεωρίας αριθμών
Εξερεύνηση πρώτων αριθμών, παραγοντοποίησης, μέγιστων κοινών διαιρετών, modular αριθμητικής και άλλων.
Όλοι οι υπολογισμοί εκτελούνται τοπικά στο πρόγραμμα περιήγησης — η είσοδος δεν ανεβαίνει ποτέ.
Λειτουργία:
Έλεγχος πρώτων αριθμών
Εισαγωγή αριθμού και κλικ στον «Έλεγχο»
Συμβουλή: Χρησιμοποιεί ντετερμινιστικό Miller-Rabin για αριθμούς έως 264.
Κλικ στο «Επόμενος πρώτος» ή «Προηγούμενος πρώτος» για εύρεση κοντινών πρώτων.
Παραγοντοποίηση σε πρώτους
Εισαγωγή αριθμού και κλικ στην «Παραγοντοποίηση»
Συμβουλή: Υποστηρίζει ακεραίους έως 1015. Ανάλυση με δέντρο παραγοντοποίησης και αναπαράσταση με εκθέτες πρώτων.
Υπολογιστής ΜΚΔ & ΕΚΠ
Εισαγωγή αριθμών και κλικ στο ΜΚΔ, ΕΚΠ ή Και τα δύο
Συμβουλή: Εισαγωγή 2 ή περισσότερων ακεραίων διαχωρισμένων με κόμμα. Το ΜΚΔ υπολογίζεται με τον αλγόριθμο του Ευκλείδη· το ΕΚΠ υπολογίζεται ως |a*b|/(a,b).
Modular αριθμητική
Εισαγωγή των a, b, m και κλικ σε μια πράξη
Συμβουλή: Η modular εκθετική χρησιμοποιεί ταχεία εκθετική (τετραγωνισμός-και-πολλαπλασιασμός).
Ο modular αντίστροφος υπάρχει μόνο όταν τα a και m είναι πρώτα μεταξύ τους.
Διαιρέτες & συναρτήσεις διαιρετών
Εισαγωγή αριθμού και κλικ στον «Υπολογισμό»
Συμβουλή: Εμφανίζει όλους τους θετικούς διαιρέτες, το πλήθος διαιρετών d(n), το άθροισμα των διαιρετών σ(n),
και τους γνήσιους διαιρέτες. Υποστηρίζει αριθμούς έως 1012.
Συνάρτηση Euler & αριθμητικές συναρτήσεις
Εισαγωγή αριθμού και κλικ στον «Υπολογισμό»
Συμβουλή: Υπολογίζει τη συνάρτηση φ του Euler φ(n), τη συνάρτηση μ του Möbius μ(n),
σ(n), d(n) και συναφείς αριθμητικές συναρτήσεις.
Πρώτοι αριθμοί και ισοτιμίες
Ένας πρώτος έχει ακριβώς δύο διαιρέτες, το 1 και τον εαυτό του· κάθε ακέραιος μεγαλύτερος του 1 παραγοντοποιείται σε πρώτους με ακριβώς έναν τρόπο (το θεμελιώδες θεώρημα της αριθμητικής). Η ισοτιμία a ≡ b (mod n) σημαίνει ότι το n διαιρεί το a−b — αριθμητική στο καντράν ρολογιού, όπου 10 + 5 ≡ 3 (mod 12)· είναι η βάση του ΜΚΔ, του ΕΚΠ και της modular εκθετικής.
Ο πολλαπλασιασμός δύο μεγάλων πρώτων είναι άμεσος, αλλά η ανάκτησή τους από το γινόμενο είναι υπολογιστικά δυσεπίλυτη — αυτή η μονόδρομη ασυμμετρία είναι η βάση της κρυπτογράφησης RSA, και γι' αυτό η φ(n) ενός modulus 2048 bit δεν είναι δημόσια.
