-
Χρειαζόμαστε μία αριθμητική διαδικασία, η οποία να είναι εύκολη προς τη μία κατεύθυνση,
-
και δύσκολη προς την άλλη.
-
Και αυτό μας οδηγεί στη χρήση αριθμητικής modulo, γνωστής και ώς αριθμητικής "ρολόι".
-
Για παράδειγμα, για να βρούμε το 46mod12, μπορούμε να πάρουμε ένα σχοινί μήκους 46 μέτρων,
-
και να το τυλίξουμε γύρω από ένα ρολόι 12 μέτρων που ονομάζεται modulist,
-
και εκεί που θα σταματήσει το σχοινί, είναι η λύση.
-
Οποτε, λέμε ότι 46mod12 είναι ισοδύναμο με 10.
-
Εύκολο.Τώρα, για να δούμε πώςδουλεύει, χρησιμοποιούμε ένα πρώτο modulist, όπως το17.
-
Μετά, βρίσκουμε μία πρώτη ρίζα του 17, σε αυτή την περίπτωση το 3,
-
η οποία έχει τη σημαντική ιδιότητα όταν την υψώνουμε σε διαφορετικούς εκθέτες,
-
η λύση διαμοιράζεται ισόνομα γύρω από το ρολόι.
-
Το 3 είναι γνωστό ώς γεννήτρια. Αν υψώσουμε το 3 σε οποιονδήποτε εκθέτη x,
-
τότε η λύση είναι εξίσου πιθανό να είναι οποιοσδήποτε ακέραιος μεταξύ του 0 και του 17.
-
Τώρα, η αντίστροφη διαδικασία είναι δύσκολη.
-
Ας πούμε, βρείτε τον εκθέτη στον οποίο πρέπει να υψωθεί το 3 για να είναι ίσο με 12.
-
Αυτό ονομάζεται Πρόβλημα Διακριτών Λογαρίθμων.
-
Και τώρα έχουμε τη συνάρτηση μίας κατεύθυνσής μας.
-
Εύκολη να υπολογίσεις, αλλά δύσκολη να αντιστρέψεις.
-
Δεδομένου τουαριθμού 12, θα έπρεπε να καταλήξουμε σε πολλές δοκιμές και λάθη μέχρι να βρούμε τον κατάλληλο εκθέτη.
-
Πόσο δύσκολο είναι αυτό;
-
Με μικρούς αριθμούς είναι εύκολο, αλλά αν χρησιμοποιήσουμε έναν πρώτο modulist ο οποίος αποτελείται από εκατοντάδες ψηφία,
-
το πρόβλημα γίνεται αδύνατο να λυθεί.
-
Ακόμα και αν είχαμε πρόσβαση σε όλη την υπολογιστική δύναμε του πλανήτη, θα έπαιρνε χιλιάδες χρόνια
-
για να τρέξουμε όλες τις πιθανές απαντήσεις.
-
Έτσι, η δύναμη μίας συνάρτησης μίας κατεύθυνσης βασίζεται στο χρόνο που χρειάζεται για να αντιστραφεί.