Πως λειτουργεί ο αλγόριθμος του Shor;

Posted on 22/05/2019

0


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

Ενώ είναι πολύ εύκολο να πολλαπλασιάσετε δύο πρώτους αριθμούς για να βρείτε το γινόμενό τους, είναι πάρα πολύ δύσκολο να αναλύσετε έναν αριθμό σε γινόμενο δύο πρώτων αριθμών και είναι πρακτικά αδύνατον αν ο αριθμός έχει πολλά ψηφία. Για να αποδείξουν ότι το κρυπτογραφικό τους σύστημα δεν μπορεί να σπάσει, οι Rivest, Shamir και Adelman ζήτησαν από όποιον νομίζει ότι μπορεί να αναλύσει σε γινόμενο δύο πρώτων αριθμών έναν ακέραιο με 129 ψηφία. Μετά από 17 χρόνια ο αριθμός αναλύθηκε από ένα δίκτυο 1.600 κλασικών υπολογιστών. Σύμφωνα με τον U. Vazirani: «ακόμη και αν κάθε σωματίδιο στο σύμπαν ήταν ένας κλασικός υπολογιστής ο οποίος θα λειτουργού σε για όλη τη μέχρι τώρα ζωή του σύμπαντος, δεν θα ήταν δυνατό να αναλυθεί σε γινόμενο δύο πρώτων αριθμών ένας ακέραιος αριθμός με 2.000 ψηφία».

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

Με έναν κβαντικό υπολογιστή απαιτείται πολυωνυμική αύξηση του χρόνου υπολογισμού για γραμμική αύξηση του μεγέθους του n, δηλαδή του αριθμού των ψηφίων του. Η μέθοδος που πρότεινε ο  Shor είναι γνωστή ως «κβαντικός αλγόριθμος του Shor»….

Διαβάστε περισσότερα ΕΔΩ:https://repository.kallipos.gr/handle/11419/223 και ΕΔΩ:https://en.wikipedia.org/wiki/Shor%27s_algorithm

Δείτε πως ο αλγόριθμος του Shor αναλύει σε παράγοντες πρώτων αριθμών τον αριθμό 314191: