Γεννήτρια τυχαίων αριθμών

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

Οι πολλές εφαρμογές της τυχαιότητας έχουν οδηγήσει στην ανάπτυξη πολλών διαφορετικών μεθόδων για την παραγωγή τυχαίων δεδομένων. Πολλές από αυτές υπάρχουν από τους αρχαίους χρόνους, όπως τα ζάρια, το ρίξιμο ενός νομίσματος, το ανακάτεμα της τράπουλας και πολλές άλλες τεχνικές. Λόγω της μηχανικής φύσεως αυτών των τεχνικών, η δημιουργία μεγάλων ακολουθιών πραγματικά τυχαίων αριθμών (κάτι σημαντικό για την στατιστική) απαιτεί πολλή εργασία και χρόνο. Έτσι, τα αποτελέσματα πολλές φορές συλλέγονταν και διανέμονταν ως πίνακες τυχαίων αριθμών. Σήμερα, μετά την έλευση των υπολογιστικών γεννητριών τυχαίων αριθμών, ένας αυξανόμενος αριθμός των κυβερνητικών λαχείων και τυχερών παιχνιδιών χρησιμοποιούν ΓΤΑ αντί για τις πιο παραδοσιακές μεθόδους. Για παράδειγμα, σήμερα χρησιμοποιούνται ΓΤΑ για να καθορίσουν τα αποτελέσματα στους σύγχρονους κουλοχέρηδες. ^[1]

Υπάρχουν αρκετές υπολογιστικές μέθοδοι για την παραγωγή τυχαίων αριθμών. Πολλές δεν μπορούν να παράγουν πραγματικά τυχαίους αριθμούς - αν και μπορούν να ανταποκριθούν, με διαφορετικούς βαθμούς επιτυχίας, σε μερικές από τις στατιστικές δοκιμασίες οι οποίες έχουν ως στόχο να μετρήσουν πόσο απρόβλεπτα είναι τα αποτελέσματά τους (δηλαδή, κατά πόσο έχουν ευδιάκριτα μοτίβα). Ωστόσο, υπάρχουν προσεκτικά σχεδιασμένα υπολογιστικά συστήματα που παράγουν τυχαίους αριθμούς με ασφάλεια, όπως αυτά που βασίζονται στον αλγόριθμο Yarrow, τον Fortuna (PRNG) και άλλους.

Εφαρμογές

Οι γεννήτριες τυχαίων αριθμών έχουν εφαρμογές σε τυχερά παιχνίδια, δειγματολειψία για στατιστικές, προσομοιώσεις, κρυπτογραφία, εντελώς τυχαίo σχεδιασμό και άλλες περιοχές όπου η παραγωγή ενός απρόβλεπτου αποτελέσματος είναι επιθυμητή. Σε γενικές γραμμές , όπου απρόβλεπτοι αριθμοί είναι υψίστης σημασίας - όπως σε εφαρμογές ασφάλειας – οι μηχανικές γεννήτριες προτιμούνται (όπου είναι εφικτό) από ψευδοτυχαίους αλγόριθμους.

Οι γεννήτριες τυχαίων αριθμών είναι πολύ χρήσιμες στους αλγόριθμους Monte Carlo και τις προσομοιώσεις, διότι η εκσφαλμάτωση διευκολύνεται από την δυνατότητα των γεννητριών να παραγάγουν την ίδια ακολουθία τυχαίων αριθμών σε πολλά τρεξίματα της ίδιας εφαρμογής. Χρησιμοποιούνται επίσης στην κρυπτογραφία – όταν ο σπόρος (seed) είναι μυστικός.

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

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

Πραγματικά τυχαίοι και ψευδοτυχαίοι αριθμοί

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

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

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

Μέθοδοι δημιουργίας

Υλικές μέθοδοι

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

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

Το 2010, ο Κάντερ et al. από το Πανεπιστήμιο του Μπαρ-Ιλάν, δημιούργησε μία φυσική γεννήτρια τυχαίων δυαδικών ψηφίων που λειτουργεί σε ποσοστό 300 gigabits ανά δευτερόλεπτο, τη γρηγορότερη που έχει μέχρι στιγμής δημιουργηθεί.^[2] Διάφοροι τρόποι συλλογής αυτής της πληροφορίας έχουν επινοηθεί. Για παράδειγμα, η ιστοσελίδα Random.org διακυμάνσεις στο πλάτος του ατμοσφαιρικού θορύβου που παράγεται από ένα κανονικό ραδιόφωνο. Μερικές τεχνικές που σχετίζονται με την ασφάλεια λογισμικού ηλεκτρονικών υπολογιστών απαιτούν από τον χρήστη να κάνει μια σειρά από κινήσεις του ποντικιού ή κτύπημα πλήκτρων ώστε να δημιουργηθεί επαρκής εντροπία που απαιτείται για τη δημιουργία τυχαίων κλειδιών ή να αρχικοποιήσει γεννήτριες ψευδοτυχαίων αριθμών. ^[3]

Υπολογιστικές μεθόδοι

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

X_{n+1}=(aX_{n}+b)\,{\textrm {mod}}\,m

για να παράγει αριθμούς. Ο μέγιστος αριθμός των αριθμών του τύπου μπορεί να παράγει είναι o συντελεστής m . Για την αποφυγή ορισμένων μη τυχαίων ιδιοτήτων της γραμμικής συμβατικής γεννήτριας, αρκετές τέτοιες γεννήτριες με ελαφρώς διαφορετικές τιμές του συντελεστή πολλαπλασιασμού A μπορούν να χρησιμοποιηθούν παράλληλα με μια "κύρια" γεννήτρια τυχαίων αριθμών να επιλέγει μεταξύ των πολλών διαφορετικών γεννητριών.^{[εκκρεμεί παραπομπή]}

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

Η ποιότητα των εν λόγω λειτουργιών ποικίλλουν ευρέως από εντελώς προβλέψιμη απόδοση, σε κρυπτογραφικά ασφαλές. Η βασική γεννήτρια τυχαίων αριθμών σε πολλές γλώσσες , συμπεριλαμβανομένης της Python, Ruby, R και PHP βασίζεται στον αλγόριθμο Mersenne Twister και 'δεν είναι επαρκής για κρυπτογραφικούς σκοπούς, όπως και αναφέρεται ρητά στην τεκμηρίωση της γλώσσας. Τέτοιες υλοποιήσεις έχουν συχνά κακές στατιστικές ιδιότητες και κάποιες επαναλαμβάνονται μετά από μόνο δέκα χιλιάδες δοκιμές . Συχνά αρχικοποιούνται χρησιμοποιώντας το ρολόι του χρόνου ενός υπολογιστή ως σπόρο, αφού το ρολόι αυτό έχει ακρίβεια χιλιοστών του δευτερολέπτου, κάτι αρκετά μεγαλύτερο από την ακρίβεια ενός ανθρώπου. Αυτές οι γεννήτριες είναι ικανοποιητικές για ορισμένες εργασίες (για παράδειγμα, βιντεοπαιχνίδια), αλλά είναι ακατάλληλα όπου απαιτείται τυχαιότητα υψηλής ποιότητας, όπως σε εφαρμογές κρυπτογραφίας, στατιστική ή αριθμητική ανάλυση.

Πολύ υψηλότερης ποιότητας πηγές τυχαίων αριθμών είναι διαθέσιμες για τα περισσότερα λειτουργικά συστήματα. Για παράδειγμα το /dev/random σε διάφορα συστήματα BSD, Linux, Mac OS X, IRIX και Solaris, ή CryptGenRandom για τα Microsoft Windows. Οι περισσότερες γλώσσες προγραμματισμού, συμπεριλαμβανομένων και των προαναφερθέντων, παρέχουν κάποια λειτουργικότητα που δίνει πρόσβαση σε αυτές τις πιο ποιοτικές πηγές.

Ένα παράδειγμα μιας απλής γεννήτριας ψευδοτυχαίων αριθμών είναι η μέθοδος multiply-with-carry του George Marsaglia. Είναι υπολογιστικά γρήγορη και έχει καλές (αν και όχι κρυπτογραφικά ισχυρές) ιδιότητες:^[4]

m_w = <επέλεξε-αρχικοποιητή>;    /* δεν πρέπει να είναι μηδέν, ούτε 0x464fffff */
m_z = <επέλεξε-αρχικοποιητή>;    /* δεν πρέπει να είναι μηδέν, ούτε 0x9068ffff */

uint get_random()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit αποτέλεσμα*/
}

Παραγωγή από κατανομή πιθανότητας

Υπάρχουν μερικές μέθοδοι που μπορούν να δημιουργήσουν έναν τυχαίο αριθμό με βάση μια συνάρτηση πυκνότητας πιθανότητας. Αυτές οι μέθοδοι περιλαμβάνουν το μετασχηματισμό με κάποιο τρόπο ενός ομοιόμορφα τυχαίου αριθμού. Εξαιτίας αυτού, αυτές οι μέθοδοι λειτουργούν εξίσου καλά στην παραγωγή ψευδοτυχαίων και αληθινά τυχαίων αριθμών. Μία μέθοδος, που ονομάζεται η μέθοδος αναστροφής, περιλαμβάνει την ενσωμάτωση επάνω σε μια περιοχή μεγαλύτερη ή ίση με τον τυχαίο αριθμό (η οποία θα πρέπει να παράγεται μεταξύ 0 και 1 για σωστές κατανομές). Μία δεύτερη μέθοδος, που ονομάζεται μέθοδος αποδοχής-απόρριψης, περιλαμβάνει την επιλογή μιας τιμής x και y και ελέγχει αν η συνάρτηση του x είναι μεγαλύτερη από την τιμή y. Αν είναι, τότε η τιμή x είναι αποδεκτή. Διαφορετικά, η τιμή του x απορρίπτεται και ο αλγόριθμος προσπαθεί ξανά.^[5]^[6]

Παραγωγή από ανθρώπους

Η παραγωγή τυχαίων αριθμών μπορεί επίσης να γίνει άμεσα από τον άνθρωπο. Ωστόσο, οι περισσότερες μελέτες δείχνουν ότι οι άνθρωποι έχουν κάποιο βαθμό μη-τυχαιότητας κατά τη δημιουργία μιας τυχαίας ακολουθίας όπως, για παράδειγμα, ψηφία ή γράμματα. Μπορεί να έχουν πολλές εναλλαγές μεταξύ επιλογών σε σχέση με μια καλή γεννήτρια τυχαίων αριθμών.^[7]

Βιβλιογραφία

↑ «Introduction to Slot Machines». Αρχειοθετήθηκε από το πρωτότυπο στις 12 Μαρτίου 2010. Ανακτήθηκε στις 14 Μαΐου 2010.
↑ Kanter, Ido; Aviad, Yaara; Reidler, Igor; Cohen, Elad; Rosenbluh, Michael. An optical ultrafast random bit generator. Nature Photonics, Volume 4, Issue 1, pp. 58–61 (2010).
↑ TrueCrypt Foundation. «TrueCrypt Beginner's Tutorial, Part 3». Ανακτήθηκε στις 27 Ιουνίου 2009.
↑ Marsaglia, George (12 Ιανουαρίου 1999). «sci.stat.math». Αρχειοθετήθηκε από το πρωτότυπο στις 5 Ιουνίου 2011. Ανακτήθηκε στις 10 Φεβρουαρίου 2010.
↑ The MathWorks. «Common generation methods». Ανακτήθηκε στις 13 Οκτωβρίου 2011. ^{[νεκρός σύνδεσμος]}
↑ The Numerical Algorithms Group. «G05 – Random Number Generators» (PDF). NAG Library Manual, Mark 23. Ανακτήθηκε στις 9 Φεβρουαρίου 2012.
↑ W. A. Wagenaar (1972). «Generation of random sequences by human subjects: a critical survey of the literature». Psychological Bulletin 77 (1): 65–72. doi:10.1037/h0032060. https://archive.org/details/sim_psychological-bulletin_1972-01_77_1/page/65.

Σύνδεσμοι

Πρότυπο:In Our Time
Clewett, James. «Random Numbers». Numberphile. Brady Haran. Αρχειοθετήθηκε από το πρωτότυπο στις 19 Μαρτίου 2016. Ανακτήθηκε στις 30 Δεκεμβρίου 2013.
jRand Αρχειοθετήθηκε 2017-04-01 στο Wayback Machine. a Java-based framework for the generation of simulation sequences, including pseudo-random sequences of numbers
Random number generators in NAG Fortran Library
Randomness Beacon at NIST, broadcasting full-entropy bit-strings in blocks of 512 bits every 60 seconds. Designed to provide unpredictability, autonomy, and consistency.

[1] «Introduction to Slot Machines». Αρχειοθετήθηκε από το πρωτότυπο στις 12 Μαρτίου 2010. Ανακτήθηκε στις 14 Μαΐου 2010.

[2] Kanter, Ido; Aviad, Yaara; Reidler, Igor; Cohen, Elad; Rosenbluh, Michael. An optical ultrafast random bit generator. Nature Photonics, Volume 4, Issue 1, pp. 58–61 (2010).

[3] TrueCrypt Foundation. «TrueCrypt Beginner's Tutorial, Part 3». Ανακτήθηκε στις 27 Ιουνίου 2009.

[4] Marsaglia, George (12 Ιανουαρίου 1999). «sci.stat.math». Αρχειοθετήθηκε από το πρωτότυπο στις 5 Ιουνίου 2011. Ανακτήθηκε στις 10 Φεβρουαρίου 2010.

[5] The MathWorks. «Common generation methods». Ανακτήθηκε στις 13 Οκτωβρίου 2011. ^{[νεκρός σύνδεσμος]}

[6] The Numerical Algorithms Group. «G05 – Random Number Generators» (PDF). NAG Library Manual, Mark 23. Ανακτήθηκε στις 9 Φεβρουαρίου 2012.

[7] W. A. Wagenaar (1972). «Generation of random sequences by human subjects: a critical survey of the literature». Psychological Bulletin 77 (1): 65–72. doi:10.1037/h0032060. https://archive.org/details/sim_psychological-bulletin_1972-01_77_1/page/65.

[1]

[2]

[3]

[4]

[5]

[6]

[7]