Ψευδοπρώτος

Ψευδοπρώτος είναι ένας ακέραιος αριθμός που μοιράζεται μια κοινή ιδιότητα με όλους τους πρώτους αριθμούς, αλλά δεν είναι στην πραγματικότητα πρώτος. Οι ψευδοπρώτοι ταξινομούνται ανάλογα με την ιδιότητα των πρώτων που ικανοποιούν.

Ορισμένες πηγές ονομάζουν ψευδοπρώτους όλους τους πιθανούς πρώτους αριθμούς, τόσο σύνθετους όσο και πρώτους.

Οι ψευδοπρώτοι έχουν πρωταρχική σημασία στην κρυπτογράφηση δημόσιου κλειδιού, η οποία βασίζεται στη δυσκολία παραγοντοποίησης μεγάλων αριθμών σε γινόμενο πρώτων παραγόντων. Ο Καρλ Πόμερανς υπολόγισε το 1988 ότι θα κόστιζε 10 εκατομμύρια δολάρια για να παραγοντοποιηθεί ένας αριθμός με 144 ψηφία και 100 δισεκατομμύρια δολάρια για να παραγοντοποιηθεί ένας αριθμός με 200 ψηφία (το κόστος σήμερα είναι δραματικά χαμηλότερο αλλά εξακολουθεί να είναι πολύ υψηλό). Αλλά η εύρεση δύο μεγάλων πρώτων αριθμών για αυτή τη χρήση είναι επίσης δαπανηρή, επομένως χρησιμοποιούνται διάφοροι μέθοδοι εύρεσης πρώτων αριθμών, μερικοί από τους οποίους σε σπάνιες περιπτώσεις δίνουν σύνθετους αριθμούς αντί για πρώτους.

Ψευδοπρώτοι του Φερμά

Το μικρό θεώρημα του Φερμά δηλώνει ότι αν το p είναι πρώτος και το α είναι σχετικά πρώτος με τον p, τότε ο αριθμός α^p−1 − 1 διαιρείται με το p. Για έναν ακέραιο αριθμό α > 1, αν ένας σύνθετος ακέραιος x διαιρεί τον α^x−1 − 1, τότε το x ονομάζεται ψευδοπρώτος του Φερμά στη βάση α. Από αυτό συνεπάγεται ότι αν το x είναι ψευδοπρώτος του Φερμά στη βάση α, τότε το x είναι σχετικά πρώτος με το α. Ορισμένες πηγές χρησιμοποιούν παραλλαγές αυτού του ορισμού, για να επιτρέψουν π.χ. μόνο στους περιττούς αριθμούς να είναι ψευδοπρώτοι.

Ένας ακέραιος x που είναι ψευδοπρώτος του Φερμά για όλες τις τιμές του α που είναι σχετικά πρώτες με το x, ονομάζεται αριθμός Καρμάικλ.