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

Στην θεωρία αριθμών, το θεώρημα του Όιλερ (γνωστό και ως θεώρημα Φερμά-Όιλερ) δηλώνει ότι για κάθε σχετικά πρώτους ακεραίους αριθμούς  και  (δηλαδή ο μέγιστος κοινός διαιρέτης του  και του  είναι το ), ισχύει ότι
, 
όπου  είναι η συνάρτηση του Όιλερ, όπου  είναι το πλήθος των ακεραίων μικρότερων του  που είναι σχετικά πρώτοι με το . Ισοδύναμα το  διαιρεί το .

Για την περίπτωση που ο  είναι πρώτος αριθμός, δηλαδή όλοι οι μικρότεροι αριθμοί  είναι σχετικά πρώτοι με το , έχουμε ότι  και έτσι
, 
που είναι το μικρό θεώρημα του Φερμά.

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

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

 Για  οι σχετικά πρώτοι αριθμοί μικρότεροι του  είναι οι  και άρα . Το θεώρημα του Όιλερ λέει ότι .
 Για  οι σχετικά πρώτοι αριθμοί μικρότεροι του  είναι οι  και άρα . Το θεώρημα του Όιλερ λέει ότι .
 Για  οι σχετικά πρώτοι αριθμοί μικρότεροι του  είναι οι  και άρα . Το θεώρημα του Όιλερ λέει ότι .

 Απόδειξη 

 Εφαρμογές 

 Υπολογισμός υπολοίπων για δυνάμεις 
Το θεώρημα χρησιμοποιείται για να επιταχυνθεί ο υπολογισμός μεγάλων δυνάμεων (με υπόλοιπο ). Για παράδειγμα για να υπολογίσουμε το , επειδή οι αριθμοί  και  είναι πρώτοι μεταξύ τους και , από το θεώρημα του Όιλερ ισχύει , έτσι έχουμε 
. 

 Αλγόριθμος RSA 
Ο αλγόριθμος RSA περιλαμβάνει την επιλογή δύο πρώτων αριθμών  και , και θέτει την παράμετρο . Έπειτα επιλέγεται ένα  που είναι σχετικά πρώτο με το . Το μήνυμα  κωδικοποιείται ως  και έπειτα αποκωδικοποιείται με τον αντίστροφο  του  στο , ως . Στο τελευταίο βήμα χρησιμοποιούμε ότι , δηλαδή το θεώρημα του Όιλερ. Αντίστοιχα, χρησιμοποιείται στο να επιταχύνουμε τον υπολογισμό του .

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

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

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


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




 Παραπομπές 

Κατηγορία:Θεωρία αριθμών