Πώς η Κβαντική Φυσική οδηγεί στην αποκρυπτογράφηση κοινών αλγορίθμων

Η άνοδος των κβαντικών υπολογιστών και της επιπτώσεις γιατί τα τρέχοντα πρότυπα κρυπτογράφησης είναι γνωστά. Αλλά γιατί ακριβώς οι κβαντικοί υπολογιστές πρέπει να είναι ιδιαίτερα ικανοί στο σπάσιμο της κρυπτογράφησης; Η απάντηση είναι μια καλή μαθηματική ταχυδακτυλουργία που ονομάζεται Αλγόριθμος Shor. Το ερώτημα που εξακολουθεί να αφήνει είναι: Τι είναι αυτό που κάνει αυτός ο αλγόριθμος που κάνει τους κβαντικούς υπολογιστές να είναι τόσο καλύτεροι στο σπάσιμο της κρυπτογράφησης; Σε αυτό το βίντεο, του YouTube μικροφυσική το εξηγεί με το παραδοσιακό του στυλ κινουμένων σχεδίων στον πίνακα.

«Ο κβαντικός υπολογισμός έχει τη δυνατότητα να τον κάνει εξαιρετικά, εξαιρετικά εύκολη την πρόσβαση σε κρυπτογραφημένα δεδομένα – όπως ένα φωτόσπαθο που μπορείτε να χρησιμοποιήσετε για να κόψετε οποιαδήποτε κλειδαριά ή φράγμα, ανεξάρτητα από το πόσο ισχυρό είναι», λέει η minutephysics. "Ο αλγόριθμος του Shor είναι αυτό το φωτόσπαθο."

Σύμφωνα με το βίντεο, ο αλγόριθμος του Shor λειτουργεί με βάση την κατανόηση ότι για οποιοδήποτε ζεύγος αριθμών, πολλαπλασιάζοντας τελικά τον έναν από τον εαυτό του θα φτάσει ο συντελεστής του άλλου αριθμού συν ή πλην 1. Έτσι, μαντεύετε τον πρώτο αριθμό και τον συνυπολογίζετε έξω, προσθέτοντας και αφαιρώντας 1, μέχρι να φτάσετε στον δεύτερο αριθμό. Αυτό θα ξεκλειδώσει την κρυπτογράφηση (συγκεκριμένα το RSA εδώ, αλλά λειτουργεί κάποιους άλλους τύπους) γιατί τότε θα είχαμε και τους δύο παράγοντες.

Ένας λόγος για τον οποίο αυτή η φαινομενικά απλή διαδικασία βασίζεται στην ανάπτυξη ισχυρών κβαντικών υπολογιστών είναι ότι η εύρεση της σωστής ισχύος για πολλαπλασιασμό του πρώτου αριθμού επί προκειμένου να βρεθεί ένας παράγοντας του δεύτερου αριθμού (N) ± 1 απαιτεί τεράστιες προσπάθειες. Το κλειδί κρυπτογράφησης είναι αρκετά μεγάλος αριθμός και επομένως η ισχύς μπορεί να είναι από 1 έως εκατομμύρια. Αλλά η ωμή βία δεν είναι ο λόγος που οι κβαντικοί υπολογιστές λειτουργούν τόσο καλά εδώ.

Οι Υπερδυνάμεις των Υπερθέσεων

Εν συντομία, χάρη στην κβαντική υπέρθεση, ένας κβαντικός υπολογιστής μπορεί να υπολογίσει πολλές απαντήσεις για μία μόνο είσοδο. Ωστόσο, το βίντεο λέει ότι λαμβάνετε μόνο μία έξοδο απάντησης κάθε φορά, με συνημμένες πιθανότητες. Για την επίλυση αυτού του προβλήματος, ο υπολογισμός ρυθμίζεται έτσι ώστε οι λανθασμένες απαντήσεις να παρεμβαίνουν μεταξύ τους, έτσι ώστε να είναι πιθανό να βγει μόνο η σωστή απάντηση (ή τουλάχιστον μια καλή εικασία). Αυτός ο υπολογισμός, ο οποίος εστιάζει στην εύρεση της σωστής ισχύος p, είναι ο αλγόριθμος του Shor.

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

Παρεμπιπτόντως, ο Peter Shor είναι ακόμα ευδοκιμεί, και αν σας ενδιαφέρει μια βαθιά βουτιά για το πώς έσπασε το Διαδίκτυο, εδώ είναι ένα άλλο βίντεο όπου ο ίδιος ο άνθρωπος εξηγεί πώς το κατάλαβε το ομώνυμο αριστούργημα του.