Θεώρημα του Όιλερ: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Χωρίς σύνοψη επεξεργασίας |
Χωρίς σύνοψη επεξεργασίας |
||
Γραμμή 17:
Εξήγηση: στο Ζ<sub>10</sub> έχουμε 1<sup>4</sup>=1, 2<sup>4</sup>=6, 3<sup>4</sup>=1, 4<sup>4</sup>=6, 5<sup>4</sup>=5, 6<sup>4</sup>=6, 7<sup>4</sup>=1, 8<sup>4</sup>=6, 9<sup>4</sup>=1. Ο Όιλερ παρατήρησε ότι το α<sup>4</sup>=1 συμβαίνει για α=1, 3, 7, 9, δηλ. όποτε οι α, 10 είναι πρώτοι μεταξύ τους.
Το θεώρημα μπορεί να χρησιμοποιηθεί για να μειωθούν εύκολα μεγάλες δυνάμεις (modulo n). Για παράδειγμα στο 7<sup>222</sup> (mod 10), επειδή οι αριθμοί 7 και 10 είναι πρώτοι μεταξύ τους και {{nowrap|1=φ(10) = φ(2 x 5) = (2-1)(5-1) = 4}}, από το θεώρημα του Όιλερ ισχύει {{nowrap|7<sup>4</sup> ≡ 1 (mod 10)}}, έτσι έχουμε 7<sup>222</sup> {{nowrap|≡ 7<sup>4 × 55 + 2</sup>}} {{nowrap|≡ (7<sup>4</sup>)<sup>55</sup> × 7<sup>2</sup>}} {{nowrap|≡ 1<sup>55</sup> × 7<sup>2</sup>}} {{nowrap|≡ 49 ≡ 9 (mod 10)}}.
Εφαρμόζεται στους αλγόριθμους [[RSA]].
Το θεώρημα του Όιλερ αποτελεί γενίκευση του [[μικρό θεώρημα του Φερμά|μικρού θεωρήματος του Φερμά]]:
| |||