Υπολογιστής συνάρτησης φ του Euler

Σχετικά με αυτόν τον υπολογιστή

Αυτός ο υπολογιστής βρίσκει τη συνάρτηση φ του Euler φ(n) — το πλήθος των θετικών ακεραίων από το 1 έως το n που είναι πρώτοι ως προς το n (δεν έχουν κοινό παράγοντα με το n εκτός του 1). Υπολογίζεται από την ανάλυση του n σε πρώτους παράγοντες χρησιμοποιώντας τον τύπο γινομένου φ(n) = n·∏(1 − 1/p) για κάθε διακριτό πρώτο παράγοντα p του n· για έναν πρώτο αριθμό p, φ(p) = p − 1.

Η συνάρτηση φ είναι κεντρική στη θεωρία αριθμών και αποτελεί το μαθηματικό θεμέλιο του κρυπτοσυστήματος δημόσιου κλειδιού RSA, όπου το φ(n) (υπολογιζόμενο από δύο μεγάλους μυστικούς πρώτους) χρησιμοποιείται για την εξαγωγή του ιδιωτικού κλειδιού από το δημόσιο κλειδί. Διέπει επίσης το θεώρημα του Euler, μια γενίκευση του μικρού θεωρήματος του Fermat που χρησιμοποιείται σε όλη την αριθμητική modulo. Εισαγάγετε έναν θετικό ακέραιο για να λάβετε την τιμή της συνάρτησης φ.