Γεννήτρια τυχαίων αριθμών: Πώς δημιουργούν οι υπολογιστές τυχαίοι αριθμοί;

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

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

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

Μέθοδοι δημιουργίας τυχαίων αριθμών

Αληθινοί τυχαίοι αριθμοί

ρομπότ ηλεκτρονικής ελεύθερης μορφής που κοιτάζει γύρω

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

Ένα τέτοιο φαινόμενο συμβαίνει έξω από τον υπολογιστή. Μετράται και ρυθμίζεται για πιθανές προκαταλήψεις λόγω της διαδικασίας μέτρησης. Παραδείγματα περιλαμβάνουν ραδιενεργή διάσπαση, φωτοηλεκτρικό φαινόμενο, κοσμική ακτινοβολία υποβάθρου, ατμοσφαιρικό θόρυβο (το οποίο θα χρησιμοποιήσουμε σε αυτό το άρθρο) και πολλά άλλα.

Έτσι, οι τυχαίοι αριθμοί που δημιουργούνται με βάση αυτή την τυχαιότητα λέγονται " αληθινοί " τυχαίοι αριθμοί.

Τεχνικά, το τμήμα υλικού αποτελείται από μια συσκευή που μετατρέπει ενέργεια από τη μία μορφή στην άλλη (για παράδειγμα, ακτινοβολία σε ηλεκτρικό σήμα), έναν ενισχυτή και έναν μετατροπέα αναλογικού σε ψηφιακό για να μετατρέψει την έξοδο σε ψηφιακό αριθμό.

Τι είναι οι Ψευδοτυχαίοι Αριθμοί;

Δυαδικός κωδικός επίθεσης χάκερ.  Κατασκευασμένο με Canon 5d Mark III και αναλογικό vintage φακό, Leica APO Macro Elmarit-R 2.8 100mm (Έτος: 1993)

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

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

Οι γεννήτριες τυχαίων αριθμών αυτού του τύπου καλούνται συχνά Pseudorandom generator generators και, ως εκ τούτου, εξάγουν Pseudorandom Numbers.

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

Ας συγκρίνουμε ορισμένες πτυχές των πραγματικών γεννητριών τυχαίων αριθμών ή TRNG s και ψευδοτυχαίων αριθμών ή PRNG s.

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

Από την άλλη πλευρά, τα TRNG δεν είναι περιοδικά και λειτουργούν καλύτερα σε ευαίσθητους στην ασφάλεια ρόλους όπως η κρυπτογράφηση.

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

Παράδειγμα αλγόριθμος για ψευδο-τυχαία γεννήτρια αριθμών

Ένας υπολογιστής εκτελεί κώδικα που βασίζεται σε ένα σύνολο κανόνων που πρέπει να ακολουθούνται. Για τα PRNGs γενικά, αυτοί οι κανόνες περιστρέφονται γύρω από τα εξής:

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

Τώρα ας δούμε ένα παράδειγμα.

Το Linear Congruential Generator

Αυτή η γεννήτρια παράγει μια σειρά ψευδοτυχαίων αριθμών. Δεδομένου ενός αρχικού σπόρου X 0 και ακέραιων παραμέτρων α ως πολλαπλασιαστής, b ως αύξησης και m ως μέτρου, η γεννήτρια ορίζεται από τη γραμμική σχέση: X n ≡ (aX n-1 + b) mod m . Ή χρησιμοποιώντας πιο φιλική σύνταξη προγραμματισμού: X n = (a * X n-1 + b)% m .

Κάθε ένα από αυτά τα μέλη πρέπει να πληροί τις ακόλουθες προϋποθέσεις:

  • m> 0 (ο συντελεστής είναι θετικός),
  • 0 <a <m (ο πολλαπλασιαστής είναι θετικός αλλά μικρότερος από τον συντελεστή),
  • 0b <m (τοη αύξηση είναι μη αρνητική αλλά μικρότερη από το συντελεστή), και
  • 0X 0 <m (ο σπόρος δεν είναι αρνητικός αλλά μικρότερος από τον συντελεστή).

Ας δημιουργήσουμε μια συνάρτηση JavaScript που παίρνει τις αρχικές τιμές ως ορίσματα και επιστρέφει έναν πίνακα τυχαίων αριθμών ενός δεδομένου μήκους:

 // x0=seed; a=multiplier; b=increment; m=modulus; n=desired array length; const linearRandomGenerator = (x0, a, b, m, n) => { const results = [] for (let i = 0; i < n; i++) { x0 = (a * x0 + b) % m results.push(x0) } return results } 

Το Linear Congruential Generator είναι ένας από τους παλαιότερους και πιο γνωστούς αλγόριθμους PRNG.

Όσον αφορά τους αλγόριθμους δημιουργίας τυχαίων αριθμών που εκτελούνται από υπολογιστές, χρονολογούνται ήδη από τη δεκαετία του 1940 και του 50 (η μέθοδος Middle-square και η γεννήτρια Lehmer, για παράδειγμα) και συνεχίζουν να γράφονται σήμερα (Xoroshiro128 +, Squares RNG και πολλά άλλα) .

Ένα δείγμα τυχαίας γεννήτριας αριθμού

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

Θα μπορούσα να χρησιμοποιήσω τη Math.random()λειτουργία JavaScript ως βάση και να δημιουργήσω έξοδο σε ψευδοτυχαίους αριθμούς όπως έχω σε προηγούμενα άρθρα (βλ. Διάγραμμα πολλαπλασιασμού - Κωδικοποιήστε τον πίνακα των δικών σας χρόνων).

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

Παρακάτω είναι η "αληθινή" γεννήτρια τυχαίων αριθμών. Ορίστε τις παραμέτρους και πατήστε Δημιουργία.

Αποτελέσματα δημιουργίας πραγματικού τυχαίου αριθμού Δυαδικό δεκαδικό δεκαεξαδικό αποτέλεσμα δημιουργίας:

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

Η τυχαιότητα προέρχεται από τον ατμοσφαιρικό θόρυβο. Μπόρεσα να χρησιμοποιήσω ασύγχρονες λειτουργίες. Αυτό είναι ένα τεράστιο όφελος στο μέλλον. Η βασική λειτουργία μοιάζει με αυτήν:

 // Δημιουργεί έναν τυχαίο αριθμό εντός του υποδεικνυόμενου από το χρήστη διαστήματος const getRandom = async (min, max, base) => { const response = await  fetch("//www.random.org/integers/?num=1&min="+min+" &max="+max+"&col=1&base="+base+"&format=plain&rnd=new") return response.text() }

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

Και πάλι, επέλεξα αυτήν τη διαμόρφωση, αλλά υπάρχουν πολλά περισσότερα διαθέσιμα στην πηγή.

Όταν κάνετε κλικ στο κουμπί Δημιουργία, handleGenerate()καλείται η συνάρτηση. Με τη σειρά του επικαλείται την getRandom()ασύγχρονη λειτουργία, διαχειρίζεται τον χειρισμό σφαλμάτων και εξάγει αποτελέσματα:

 // Output handling const handleGenerate = () => { handleActive(generateButton) const base = binary.checked ? 2 : decimal.checked ? 10 : 16 if (!minimum.value || !maximum.value) { prompter.style.color = 'red' prompter.textContent = "Enter Min & Max values" } else { getRandom(minimum.value, maximum.value, base).then((data) => { resultValue.textContent = data prompter.textContent = "" }).catch((error) => { resultValue.textContent = 'ERROR' prompter.textContent = 'Connection error. Unable to generate'; }) handleRestart() } } 

Ο υπόλοιπος κώδικας ασχολείται με τη δομή HTML, την εμφάνιση και το στυλ.

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

Αυτός είναι ο σύνδεσμος προς το repo GitHub του πλήρους κώδικα: //github.com/sandroarobeli/random-generator