Όπως ήδη έχει αναφερθεί πρώτος λέγεται ο θετικός αριθμός που διαιρείται μόνο με τον εαυτό του και τη μονάδα, π.χ. 2,3,5,7,11,13,17...
Κάθε άλλος αριθμός λέγεται σύνθετος, π.χ. 4,6,9,10,12,14,15,16,18. Κάθε δε σύνθετος αριθμός μπορεί να γραφεί με μοναδικό τρόπο ως γινόμενο δυνάμεων πρώτων αριθμών, π.χ. 1764381125=53x132x174 και 4695768=23x32x72x113.
Το θεμελιώδες θεώρημα των πρώτων αριθμών μας λέει ότι το πλήθος π(x) των πρώτων που είναι μικρότεροι του x ισχύει ό διπλανός τύπος. Όσο μεγαλύτερο το x τόσο πιο ακριβές το αποτέλεσμα.
Για παράδειγμα, με βάση το θεώρημα, μέχρι το 1000 υπάρχουν περίπου 1000/ln(1000) πρώτοι αριθμοί που είναι 145. Δηλαδή η πυκνότητά τους είναι 1000/145≈7 που σημαίνει ότι αν επιλέξουμε 7 τυχαίους αριθμούς στο διάστημα 1-1000 ένας από αυτούς θα είναι πρώτος. Δοκιμάστε το !!
Κάθε άλλος αριθμός λέγεται σύνθετος, π.χ. 4,6,9,10,12,14,15,16,18. Κάθε δε σύνθετος αριθμός μπορεί να γραφεί με μοναδικό τρόπο ως γινόμενο δυνάμεων πρώτων αριθμών, π.χ. 1764381125=53x132x174 και 4695768=23x32x72x113.
Το θεμελιώδες θεώρημα των πρώτων αριθμών μας λέει ότι το πλήθος π(x) των πρώτων που είναι μικρότεροι του x ισχύει ό διπλανός τύπος. Όσο μεγαλύτερο το x τόσο πιο ακριβές το αποτέλεσμα.
Για παράδειγμα, με βάση το θεώρημα, μέχρι το 1000 υπάρχουν περίπου 1000/ln(1000) πρώτοι αριθμοί που είναι 145. Δηλαδή η πυκνότητά τους είναι 1000/145≈7 που σημαίνει ότι αν επιλέξουμε 7 τυχαίους αριθμούς στο διάστημα 1-1000 ένας από αυτούς θα είναι πρώτος. Δοκιμάστε το !!
Πώς αναλύεται ένας αριθμός
Σε σύνθετο αριθμό n αρκεί να ελεγχθούν οι παράγοντες που είναι μικρότεροι του n1/2. Οπότε αναζητείται πρώτος διαιρέτης του n ξεκινώντας από το 2. Αν βρεθεί διαιρέτης του και δίνει πηλίκο π τότε εφαρμόζεται η ίδια διαδικασία στο πηλίκο π, δηλαδή αναζητείται πρώτος διαιρέτης του π ξεκινώντας από τον διαιρέτη του προηγούμενου βήματος και μέχρι το π1/2. Η τακτική αυτή εφαρμόζεται μέχρι εξαντλήσεως. Παράδειγμα να αναλυθεί ο 225277.
Ελέγχοντας διαδοχικά το 2,3,5,7,11 διαπιστώνεται ότι δεν είναι διαιρέτες του. Το 13 όμως είναι και δίνει πηλίκο π=17329. Ελέγχοντας το π ξεκινώντας από το 13 διαπιστώνεται ότι διαιρεί το πηλίκο και δίνει νέο πηλίκο π=1333. Τώρα το 36 < 13331/2 άρα ξεκινώντας από το 13 και δοκιμάζοντας διαδοχικά το 17,19,23,29 καταλήγει στο 31 που είναι διαιρέτης του 1333 με πηλίκο το 43, η διαδικασία ολοκληρώνεται. Συγκεντρώνοντας τους πρώτους διαιρέτες η ανάλυση καταλήγει στο 225277 = 132 x 31 x 43. Να σημειωθεί ότι δεν είναι γνωστοί οι πρώτοι. Αν ο αρχικός αριθμός n επιλεγεί κατάλληλα ώστε ο πρώτος παράγοντάς του να είναι πολύ μεγάλος αριθμός, εύκολα συμπεραίνεται ότι η μέθοδος είναι πρακτικά ανεφάρμοστη.
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
by: Πληροφορική Online
Πληροφορική Online Updated at: 2:56 μ.μ.