Θεώρημα του Όιλερ

Στην θεωρία αριθμών, το θεώρημα του Όιλερ (γνωστό και ως θεώρημα Φερμά-Όιλερ) δηλώνει ότι για κάθε σχετικά πρώτους ακεραίους αριθμούς $a$ και $n$ (δηλαδή ο μέγιστος κοινός διαιρέτης του $a$ και του $n$ είναι το $1$), ισχύει ότιΠρότυπο:RpΠρότυπο:RpΠρότυπο:RpΠρότυπο:Rp

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$,

όπου $\phi$ είναι η συνάρτηση του Όιλερ, όπου $\phi (n)$ είναι το πλήθος των ακεραίων μικρότερων του $n$ που είναι σχετικά πρώτοι με το $n$. Ισοδύναμα το $n$ διαιρεί το $a^{\phi (n)}-1$.

Για την περίπτωση που ο $n$ είναι πρώτος αριθμός, δηλαδή όλοι οι μικρότεροι αριθμοί $1,2,3,\dots ,n-1$ είναι σχετικά πρώτοι με το $n$, έχουμε ότι $\phi (n)=n-1$ και έτσι

$a^{n-1}\equiv 1(\mathrm{mod}n)$,

που είναι το μικρό θεώρημα του Φερμά.

Το θεώρημα παίρνει το όνομά του από τον μαθηματικό Λέοναρντ Όιλερ και βρίσκει εφαρμογές σε διάφορους τομείς της κρυπτογραφίας και συγκεκριμένα στο κρυπτοσύστημα RSA. Το θεώρημα του Όιλερ γενικεύεται από την συνάρτηση του Κάρμαϊκλ.

Παραδείγματα

• Για $n=5$ οι σχετικά πρώτοι αριθμοί μικρότεροι του $n$ είναι οι $a=1,2,3,4$ και άρα $\phi (n)=4$. Το θεώρημα του Όιλερ λέει ότι $1^4\equiv 2^4\equiv 3^4\equiv 4^4\equiv 1(\mathrm{mod}5)$.
• Για $n=6$ οι σχετικά πρώτοι αριθμοί μικρότεροι του $n$ είναι οι $a=1,5$ και άρα $\phi (n)=2$. Το θεώρημα του Όιλερ λέει ότι $1^2\equiv 5^2\equiv 1(\mathrm{mod}6)$.
• Για $n=10$ οι σχετικά πρώτοι αριθμοί μικρότεροι του $n$ είναι οι $a=1,3,7,9$ και άρα $\phi (n)=4$. Το θεώρημα του Όιλερ λέει ότι $1^4\equiv 3^4\equiv 7^4\equiv 9^4\equiv 1(\mathrm{mod}10)$.

Εφαρμογές

Υπολογισμός υπολοίπων για δυνάμεις

Το θεώρημα χρησιμοποιείται για να επιταχυνθεί ο υπολογισμός μεγάλων δυνάμεων (με υπόλοιπο $n$). Για παράδειγμα για να υπολογίσουμε το $7^{222}(\mathrm{mod}10)$, επειδή οι αριθμοί $7$ και $10$ είναι πρώτοι μεταξύ τους και $\phi (10)=\phi (2\cdot 5)=(2-1)\cdot (5-1)=4$, από το θεώρημα του Όιλερ ισχύει $7^4\equiv 1(\mathrm{mod}10)$, έτσι έχουμε

$7^{222}\equiv 7^{4\cdot 55+2}\equiv (7^4{)}^{55}\cdot 7^2\equiv 1^{55}\cdot 7^2\equiv 49\equiv 9(\mathrm{mod}10)$.

Αλγόριθμος RSA

Ο αλγόριθμος RSA περιλαμβάνει την επιλογή δύο πρώτων αριθμών $p$ και $q$, και θέτει την παράμετρο $n=p\cdot q$. Έπειτα επιλέγεται ένα $e$ που είναι σχετικά πρώτο με το $n$. Το μήνυμα $m$ κωδικοποιείται ως $m^e\mathrm{m}\mathrm{o}\mathrm{d}n$ και έπειτα αποκωδικοποιείται με τον αντίστροφο $d$ του $m$ στο ${\mathbb{Z}}_{\phi (n)}$, ως $(m^e{)}^d\equiv m^{ed}\equiv m(\mathrm{mod}n)$. Στο τελευταίο βήμα χρησιμοποιούμε ότι $m^{\phi (n)}\equiv 1(\mathrm{mod}n)$, δηλαδή το θεώρημα του Όιλερ. Αντίστοιχα, χρησιμοποιείται στο να επιταχύνουμε τον υπολογισμό του $m^e\mathrm{m}\mathrm{o}\mathrm{d}n$.

Δείτε επίσης

• Μικρό θεώρημα του Φερμά
• Συνάρτηση του Όιλερ
• Συνάρτηση του Κάρμαϊκλ

Περαιτέρω ανάγνωση

Ελληνικά άρθρα

• Πρότυπο:Cite journal

Ξενόγλωσσα άρθρα

• Πρότυπο:Cite journal
• Πρότυπο:Cite journal
• Πρότυπο:Cite journal