Ημιπρώτοι αριθμοί

Οι ημιπρώτοι αριθμοί είναι φυσικοί αριθμοί οι οποίοι αποτελούν το γινόμενο 2 πρώτων αριθμών. Εξ ορισμού οι αριθμοί αυτοί δεν διαθέτουν σύνθετους αριθμούς ως παράγοντες, παρά μόνο τους πρώτους αριθμούς των οποίων αποτελούν γινόμενο, και τον εαυτό τους και το 1.Έχουν ευρεία χρήση στους αλγορίθμους που βασίζονται στην κρυπτογράφηση με χρήση δημοσίου κλειδιού.

Περιγραφή

Ο συνολικός αριθμός των πρώτων αριθμών οι οποίοι είναι παράγοντες ενός ημιπρώτου αριθμού είναι πάντα 2. Ένας ημιπρώτος αριθμός μπορεί να είναι γινόμενο διαφορετικών πρώτων αριθμών, ή το τετράγωνο ενός πρώτου αριθμού, και εξ'ορισμού όλα τα τετράγωνα πρώτων είναι ημιπρώτοι αριθμοί. Ακολούθως, ο μεγαλύτερος γνωστός ημιπρώτος αριθμός είναι πάντα το τετράγωνο του μεγαλύτερου γνωστού πρώτου αριθμού, εκτός και αν οι παράγοντες του ημιπρώτου δεν είναι γνωστοί.

Είναι πιθανό να αποδειχθεί πως κάποιος αριθμός είναι ημιπρώτος χωρίς να είναι γνωστοί οι παράγοντες του. Ένας σύνθετος αριθμός $n$ ο οποίος δεν διαιρείται με τους πρώτους ως $\leq {\sqrt[{3}]{n}}$ είναι ημιπρώτος αριθμός. Υπάρχουν διάφορες μέθοδοι, όπως οι ελλιπτικές ψευδοκαμπύλες και το θεώρημα Goldwasser-Kilian ECPP οι οποίες μπορούν να χρησιμοποιηθούν για την εύρεση μεγάλων ημιπρώτων για τους οποίους αγνοούνται οι πρώτοι αριθμοί της παραγοντοποίησης τους. Οι μέθοδοι αυτοί αποτελούν την εξαίρεση κατά περίπτωση, καθώς είναι απλούστερη η εύρεση των πρώτων αριθμών μέσω πολλαπλασιασμού.

Οι αρχικοί ημιπρώτοι αριθμοί οι οποίοι είναι μικρότεροι από το 100 είναι οι 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, και 95. (ακολουθία A001358 στην OEIS). Οι ημιπρώτοι οι οποίοι δεν είναι τέλεια τετράγωνα, ονομάζονται διακριτοί ημιπρώτοι αριθμοί.

Υπολογισμοί συναρτήσεων

Για έναν ημιπρώτο αριθμό n = pq η τιμή της συνάρτησης Όιλερ (πόσοι θετικοί αριθμοί είναι μικρότεροι ή ίσοι με το n οι οποίοι είναι σχετικά πρώτοι με το n) όταν οι πρώτοι p και q είναι διαφορετικοί:

φ(n) = (p − 1) (q − 1) = p q − (p + q) + 1 = n − (p + q) + 1.

ενώ εάν είναι οι ίδιοι:

φ(n) = φ(p²) = (p − 1) p = p² − p = n − p.

Η συνάρτηση ζήτα πρώτων αριθμών μπορεί να εφαρμοστεί στους ημιπρώτους αριθμούς, με ορισμό σταθερών όπως:

$\sum _{\Omega (n)=2}{\frac {1}{n^{2}}}\approx 0.1407604$ (ακολουθία A117543 στην OEIS)

$\sum _{\Omega (n)=2}{\frac {1}{n(n-1)}}\approx 0.17105$ (ακολουθία A152447 στην OEIS)

$\sum _{\Omega (n)=2}{\frac {\ln n}{n^{2}}}\approx 0.28360$ (ακολουθία A154928 στην OEIS)

Εφαρμογές

Οι ημιπρώτοι αριθμοί είναι εξαιρετικά χρήσιμοι στους τομείς της κρυπτογραφίας και της θεωρίας αριθμών, κυρίως σε ότι αφορά την κρυπτογράφηση με χρήση δημοσίου κλειδιού όπου και χρησιμοποιούνται από αλγορίθμους όπως τον RSA. Η χρήση τους βασίζεται στο γεγονός ότι είναι απλό να οριστεί ένας μεγάλος ημιπρώτος αριθμός καθώς το μόνο που απαιτείται είναι το γινόμενο 2 πρώτων αριθμών, ωστόσο μπορεί να είναι δύσκολο να βρεθεί το ποιοι ήταν οι πρώτοι αριθμοί αυτοί αν το μόνο που υπάρχει διαθέσιμο είναι ο ημιπρώτος αριθμός.

Στην πρακτική κρυπτογραφία, αποφεύγεται η χρήση των οποιονδήποτε ημιπρώτων αριθμών, καθώς υπάρχουν αλγόριθμοι οι οποίοι είναι προσαρμοσμένοι στο να βρίσκουν γρήγορα τους παράγοντες ημιπρώτων αριθμών όπου οι παράγοντες είναι συγκεκριμένου τύπου πρώτοι αριθμοί. Έτσι οι πρώτοι αριθμοί p και q το γινόμενο των οποίων ισούται με n, πρέπει να είναι αρκετά μεγάλοι, σε αναλογία με την τετραγωνική ρίζα του n, έτσι ώστε η εύρεση τους να είναι υπολογιστικά ακριβή. Επίσης οι p και q δεν πρέπει να είναι πολύ κοντά ο ένας στον άλλο, διαφορετικά θα βρεθούν μέσω της μεθόδου παραγοντοποίησης Φερμά.

Το 1974, το μήνυμα του Αρεσίμπο δημιουργήθηκε έτσι ώστε να αποτελείται από 1679 δυαδικά ψηφία, έτσι ώστε να μπορεί να ερμηνευτεί από τους πιθανούς παραλήπτες πως αποτελείται από 23 γραμμές επί 73 στήλες.

Δείτε επίσης

• Πρώτοι αριθμοί Τσεν

Εξωτερικοί σύνδεσμοι

• Weisstein, Eric W., "Semiprime" από το MathWorld.