Πώς να δημιουργήσετε έναν μεγάλο πρώτο αριθμό | Περιοδικό Quanta

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

Αλλά είναι. Η κατασκευή αυθαίρετα μεγάλων πρώτων αριθμών είναι εξαιρετικά περίπλοκη. Βασικά έχετε δύο υπολογιστικές επιλογές, και οι δύο με μειονεκτήματα. Θα μπορούσατε να χρησιμοποιήσετε την τυχαιότητα και να βρείτε ένα μαντεύοντας, αλλά η μέθοδος είναι ασυνεπής — διατρέχετε τον κίνδυνο να δημιουργείτε διαφορετικό πρώτο κάθε φορά. Ή θα μπορούσατε να χρησιμοποιήσετε έναν πιο αξιόπιστο, ντετερμινιστικό αλγόριθμο, αλλά με βαρύ υπολογιστικό κόστος.

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

«Έκαναν μια ακολουθία προσπαθειών, καθεμία από αυτές προσπαθώντας να κατασκευάσει έναν πρώτο αριθμό διαφορετικού μήκους, και έδειξαν ότι μια από τις προσπάθειες λειτουργεί», είπε. Roei Tell, θεωρητικός επιστήμονας υπολογιστών στο Ινστιτούτο Προηγμένων Μελετών που δεν ασχολήθηκε με την εργασία. "Είναι μια κατασκευή που βγάζει έναν ντετερμινιστικά επιλεγμένο πρώτο, αλλά σας επιτρέπει να πετάτε νομίσματα και να κάνετε τυχαίες επιλογές στη διαδικασία."

Η πρόκληση να φτιάξεις μια αποτελεσματική συνταγή για πρώτες θέσεις έχει βαθιές ρίζες. «Πραγματικά δεν γνωρίζουμε τόσα πολλά για το πώς κατανέμονται οι πρώτοι, ή για τα κενά στους πρώτους», είπε ο Ofer Grossman, ο οποίος μελετά τους ψευδοτυχαίους αλγόριθμους. Και αν δεν ξέρουμε πού να τους βρούμε, δεν υπάρχει εύκολος τρόπος να δημιουργήσουμε έναν πρώτο αριθμό από την αρχή.

Με την πάροδο του χρόνου, οι ερευνητές ανέπτυξαν τις προαναφερθείσες προσεγγίσεις. Ο απλούστερος τρόπος είναι απλώς να μαντέψεις. Εάν θέλετε έναν πρώτο με 1,000 ψηφία, για παράδειγμα, μπορείτε να επιλέξετε έναν αριθμό 1,000 ψηφίων τυχαία και μετά να τον ελέγξετε. "Αν δεν είναι πρωταρχικό, απλά δοκιμάζεις άλλο ένα, και άλλο, και ούτω καθεξής μέχρι να βρεις ένα", είπε Ραχούλ Σαντάναμ, επιστήμονας υπολογιστών στο Πανεπιστήμιο της Οξφόρδης και συν-συγγραφέας της νέας εργασίας. "Επειδή υπάρχουν πολλοί πρώτοι αριθμοί, αυτός ο αλγόριθμος θα σας δώσει κάποιον πρώτο αριθμό με μεγάλη πιθανότητα, μετά από έναν σχετικά μικρό αριθμό επαναλήψεων." Αλλά η χρήση της τυχαιότητας σημαίνει ότι πιθανότατα θα λαμβάνετε διαφορετικό αριθμό κάθε φορά, είπε. Αυτό θα μπορούσε να είναι πρόβλημα εάν χρειάζεστε συνέπεια — εάν, για παράδειγμα, χρησιμοποιείτε μια κρυπτογραφική μέθοδο ασφάλειας που εξαρτάται από τη διαθεσιμότητα μεγάλων πρώτων.

Η άλλη προσέγγιση είναι να ακολουθήσουμε έναν ντετερμινιστικό αλγόριθμο. Θα μπορούσατε να επιλέξετε ένα σημείο εκκίνησης και να αρχίσετε να δοκιμάζετε αριθμούς, διαδοχικά, για πρωταρχικό χαρακτήρα. Τελικά είστε προορισμένοι να βρείτε ένα και ο αλγόριθμός σας θα βγάζει με συνέπεια τον πρώτο που θα βρείτε. Αλλά μπορεί να χρειαστεί λίγος χρόνος: Αν ψάχνετε για έναν πρώτο αριθμό με 1,000 ψηφία, ακόμη και έναν υπολογισμό με 2⁵⁰⁰ Τα βήματα - που θα διαρκούσαν πολύ περισσότερο από την ηλικία του σύμπαντος - δεν είναι αρκετά για να εγγυηθούν την επιτυχία.

Το 2009, ο μαθηματικός και ο μετάλλιος Fields Terence Tao ήθελε να τα πάει καλύτερα. Προκάλεσε τους μαθηματικούς να βρουν έναν ντετερμινιστικό αλγόριθμο για την εύρεση ενός πρώτου ενός δεδομένου μεγέθους εντός ενός υπολογιστικού χρονικού ορίου.

Αυτό το χρονικό όριο είναι γνωστό ως πολυωνυμικός χρόνος. Ένας αλγόριθμος λύνει ένα πρόβλημα σε πολυωνυμικό χρόνο εάν ο αριθμός των βημάτων που κάνει δεν είναι περισσότερο από μια πολυωνυμική συνάρτηση του n, το μέγεθος της εισόδου. (Μια πολυωνυμική συνάρτηση περιλαμβάνει όρους που έχουν μεταβλητές αυξημένες σε θετικές ακέραιες δυνάμεις, π.χ n² ή 4n³.) Στο πλαίσιο της κατασκευής πρώτων αριθμών, n αναφέρεται στον αριθμό των ψηφίων στον πρώτο που θέλετε. Υπολογιστικά μιλώντας, αυτό δεν κοστίζει πολύ: Οι επιστήμονες υπολογιστών περιγράφουν προβλήματα που μπορούν να λυθούν με αλγόριθμους σε πολυωνυμικό χρόνο ως εύκολα. Ένα δύσκολο πρόβλημα, αντίθετα, απαιτεί εκθετικό χρόνο, πράγμα που σημαίνει ότι απαιτεί έναν αριθμό βημάτων που προσεγγίζονται από μια εκθετική συνάρτηση (η οποία περιλαμβάνει όρους όπως 2ⁿ).

Για δεκαετίες, οι ερευνητές έχουν ερευνήσει τη σύνδεση μεταξύ τυχαίας και σκληρότητας. Το πρόβλημα κατασκευής των πρώτων αριθμών θεωρείτο εύκολο αν επέτρεπες την τυχαιότητα — και ήσουν ικανοποιημένος με τη λήψη διαφορετικού αριθμού κάθε φορά — και δύσκολο αν επέμενες στον ντετερμινισμό.

Κανείς δεν έχει καταφέρει ακόμα να ανταποκριθεί στην πρόκληση του Tao, αλλά η νέα δουλειά πλησιάζει. Βασίζεται σε μεγάλο βαθμό σε μια προσέγγιση που εισήχθη το 2011 από τους Shafi Goldwasser και Eran Gat, επιστήμονες υπολογιστών στο Ινστιτούτο Τεχνολογίας της Μασαχουσέτης. Περιέγραψαν «ψευδοδετερμινιστικούς» αλγόριθμους - μαθηματικές συνταγές για προβλήματα αναζήτησης, όπως η εύρεση μεγάλων πρώτων, που θα μπορούσαν να εκμεταλλευτούν τα οφέλη της τυχαιότητας και, με μεγάλη πιθανότητα, εξακολουθούν να παράγουν την ίδια απάντηση κάθε φορά. Θα χρησιμοποιούσαν την αποτελεσματικότητα των τυχαίων δυαδικών ψηφίων στη συνταγή, τα οποία θα αποτυχαιοποιούνταν στο αποτέλεσμα, εμφανίζοντας ντετερμινιστικά.

Οι ερευνητές εξερευνούν από τότε ψευδοντετερμινιστικούς αλγόριθμους. Το 2017, ο Santhanam και ο Igor Oliveira από το Πανεπιστήμιο του Warwick (ο οποίος συνέβαλε επίσης στη νέα δουλειά) περιγράφεται μια ψευδοδετερμινιστική προσέγγιση για την κατασκευή πρώτων που χρησιμοποιούσε τυχαιότητα και φαινόταν πειστικά ντετερμινιστική, αλλά λειτούργησε σε «υποεκθετικό» χρόνο — ταχύτερο από τον εκθετικό, αλλά πιο αργό από τον πολυωνυμικό χρόνο. Στη συνέχεια, το 2021, το Tell and Lijie Chen, επιστήμονας υπολογιστών στο Πανεπιστήμιο της Καλιφόρνια στο Μπέρκλεϋ, διερευνηθεί πώς να χρησιμοποιήσετε ένα δύσκολο πρόβλημα για να δημιουργήσετε μια γεννήτρια ψευδοτυχαίων αριθμών (αλγόριθμος που δημιουργεί μια σειρά αριθμών που δεν διακρίνονται από μια τυχαία έξοδο). «Βρήκαμε μια νέα σύνδεση μεταξύ της σκληρότητας και της ψευδοτυχαίας», είπε ο Τσεν.

Τα κομμάτια τελικά ενώθηκαν την άνοιξη του 2023, κατά τη διάρκεια ένα bootcamp για την υπολογιστική πολυπλοκότητα στο Ινστιτούτο Simons για τη Θεωρία των Υπολογιστών στο Μπέρκλεϋ, όταν οι ερευνητές άρχισαν να εργάζονται μαζί για το πρόβλημα, συνδυάζοντας προηγούμενα αποτελέσματα. Για το νέο έργο, είπε ο Τσεν, ο Χάνλιν Ρεν - επιστήμονας υπολογιστών στην Οξφόρδη και συν-συγγραφέας - είχε τις αρχικές ιδέες να συνδυάσει το αποτέλεσμα Chen-Tell με την προσέγγιση Santhanam-Oliveira με έναν νέο τρόπο. Στη συνέχεια, όλη η ομάδα ανέπτυξε τις ιδέες πληρέστερα για την παραγωγή του νέου χαρτιού.

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

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

«Θα ήταν ωραίο να απαλλαγούμε από αυτή τη μικρή προειδοποίηση», είπε ο Γκρόσμαν.

Ο απώτερος στόχος, είπε ο Santhanam, είναι να βρεθεί ένας αλγόριθμος που δεν απαιτεί καθόλου τυχαιότητα. Αλλά αυτή η αναζήτηση παραμένει ανοιχτή. «Ο ντετερμινισμός είναι αυτό που θα θέλαμε να χρησιμοποιήσουμε», είπε.

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

«Είναι συναρπαστικό να προσπαθείς να σκεφτείς πού αλλού θα οδηγήσουν αυτές οι λαμπρές παρατηρήσεις», είπε ο Τελ.