Πρώτοι λέγονται οι θετικοί ακέραιοι που διαιρούνται μόνο από δυο αριθμούς τον εαυτό τους και τη μονάδα.
Έτσι πρώτοι αριθμοί είναι οι 2, 3, 5, 7, 11, 13, 17 ....
Η μονάδα δεν είναι πρώτος αριθμός. Όλοι οι άλλοι αριθμοί λέγονται σύνθετοι και μπορούν να εκφραστούν ως γινόμενο πρώτων αριθμών.
Παράδειγμα το 3361743 είναι σύνθετος αριθμός και μπορεί να γραφεί ως 3361743=34x73x112
Δύο θετικοί ακέραιοι α, β ονομάζονται σχετικοί πρώτοι και συμβολίζονται με (α,β)=1 όταν δεν έχουν μεταξύ τους κανένα κοινό διαιρέτη.
Για παράδειγμα (13, 42), (25, 27)
Αντίστροφοι ακέραιοι κατά mod n ονομάζονται δυο θετικοί ακέραιοι α και β αν ισχύει α x β=1 mod n. Παράδειγμα ο αντίστροφος του 12 mod 25 είναι το 23 γιατί (12 x 23 =276=11x25 +1)=1 mod 25.
Για να υπάρχει ο αντίστροφος του α κατά mod n πρέπει ο α και ο n να είναι σχετικά πρώτοι μεταξύ τους (α,η)=1.
Παράδειγμα ο 5, 10, 15, 20 κατά mod 25 δεν έχουν αντίστροφο ενώ όπως είδαμε ο 12 έχει το 23, ο 7 έχει το 18, ο 8 έχει τον 22 κ.λ.π.
Κρυπτογραφία Σινάτκας
Έτσι πρώτοι αριθμοί είναι οι 2, 3, 5, 7, 11, 13, 17 ....
Η μονάδα δεν είναι πρώτος αριθμός. Όλοι οι άλλοι αριθμοί λέγονται σύνθετοι και μπορούν να εκφραστούν ως γινόμενο πρώτων αριθμών.
Παράδειγμα το 3361743 είναι σύνθετος αριθμός και μπορεί να γραφεί ως 3361743=34x73x112
Δύο θετικοί ακέραιοι α, β ονομάζονται σχετικοί πρώτοι και συμβολίζονται με (α,β)=1 όταν δεν έχουν μεταξύ τους κανένα κοινό διαιρέτη.
Για παράδειγμα (13, 42), (25, 27)
Αντίστροφοι ακέραιοι κατά mod n ονομάζονται δυο θετικοί ακέραιοι α και β αν ισχύει α x β=1 mod n. Παράδειγμα ο αντίστροφος του 12 mod 25 είναι το 23 γιατί (12 x 23 =276=11x25 +1)=1 mod 25.
Για να υπάρχει ο αντίστροφος του α κατά mod n πρέπει ο α και ο n να είναι σχετικά πρώτοι μεταξύ τους (α,η)=1.
Παράδειγμα ο 5, 10, 15, 20 κατά mod 25 δεν έχουν αντίστροφο ενώ όπως είδαμε ο 12 έχει το 23, ο 7 έχει το 18, ο 8 έχει τον 22 κ.λ.π.
Κρυπτογραφία Σινάτκας
by: Πληροφορική Online
Πληροφορική Online Updated at: 2:09 μ.μ.