|
Μια '''γεννήτρια τυχαίων αριθμών''' είναι μια [[computerΥπολογιστής|υπολογιστική]] ή μηχανική συσκευή που έχει σχεδιαστεί για να παράγει μια ακολουθία αριθμών ή συμβόλων που δεν ακολουθούν κάποιο μοτίβο, δηλαδή εμφανίζονται [[randomΤυχαίο συμβάν|τυχαία]].
Οι πολλές εφαρμογές της τυχαιότητας έχουν οδηγήσει στην ανάπτυξη πολλών διαφορετικών μεθόδων για την παραγωγή τυχαίων δεδομένων. Πολλές από αυτές υπάρχουν από τους αρχαίους χρόνους, όπως τα [[dice|ζάρια]], το [[coin flipping|ρίξιμο ενός νομίσματος]], το [[shuffling||ανακάτεμα]] της [[playing card|Τράπουλα|τράπουλας]] και πολλές άλλες τεχνικές. Λόγω της μηχανικής φύσεως αυτών των τεχνικών, η δημιουργία μεγάλων ακολουθιών πραγματικά τυχαίων αριθμών (κάτι σημαντικό για την στατιστική) απαιτεί πολλή εργασία και χρόνο. Έτσι, τα αποτελέσματα πολλές φορές συλλέγονταν και διανέμονταν ως [[random number table|πίνακες τυχαίων αριθμών]]. Σήμερα, μετά την έλευση των υπολογιστικών γεννητριών τυχαίων αριθμών, ένας αυξανόμενος αριθμός των κυβερνητικών λαχείων και τυχερών παιχνιδιών χρησιμοποιούν ΓΤΑ αντί για τις πιο παραδοσιακές μεθόδους. Για παράδειγμα, σήμερα χρησιμοποιούνται ΓΤΑ για να καθορίσουν τα αποτελέσματα στους σύγχρονους [[slot machine|κουλοχέρηδες]]. <ref>{{cite web
| title = Introduction to Slot Machines
| url = http://slotsvariations.com/slot-machine.htm
== Εφαρμογές ==
{{Main|Εφαρμογές Τυχαίων Αριθμών}}
{{Main|Applications of randomness}}
Οι γεννήτριες τυχαίων αριθμών έχουν εφαρμογές σε [[gambling|τυχερά παιχνίδια]], [[statisticalΔείγμα sampling(στατιστική)|δειγματολειψία για στατιστικές]], [[computer simulationΠροσομοίωση|προσομοιώσεις]], [[cryptography|κρυπτογραφία]], [[completelyεντελώς randomizedτυχαίος designσχεδιασμός|εντελώς τυχαίo σχεδιασμό]] και άλλες περιοχές όπου η παραγωγή ενός απρόβλεπτου αποτελέσματος είναι επιθυμητή.
Σε γενικές γραμμές , όπου απρόβλεπτοι αριθμοί είναι υψίστης σημασίας - όπως σε εφαρμογές ασφάλειας – οι μηχανικές γεννήτριες προτιμούνται ( όπου είναι εφικτό ) από ψευδοτυχαίους αλγόριθμους.
=== Υλικές μεθόδοι ===
{{Main|Υλική γεννήτρια τυχαίων αριθμών}}
{{Main|Hardware random number generator}}
Οι παλαιότερες μεθόδοι για την παραγωγή τυχαίων αριθμών - [[dice|ζάρια]], [[coinΡίξιμο flippingνομίσματος|ρίξιμο ενός νομίσματος]], τροχοί [[rouletteΡουλέτα|ρουλέτας]] - χρησιμοποιούνται ακόμα και σήμερα, κυρίως μόνο στα παιχνίδια και τα τυχερά παιχνίδια, διότι είναι πολύ αργές για τις περισσότερες εφαρμογές της στατιστικής και κρυπτογραφίας.
Μια υλική γεννήτρια τυχαίων αριθμών μπορεί να βασίζεται σε ένα τυχαίο ατομικό ή υποατομικό φυσικό φαινόμενο του οποίου η απροβλεπτικότητα μπορεί να αποδοθεί στους νόμους της [[quantumΚβαντική mechanicsμηχανική|κβαντικής μηχανικής]]. Πηγές [[entropy (information theory)Εντροπία|εντροπίας]] περιλαμβάνουν [[radioactiveΡαδιενεργός decayισορροπία|ραδιενεργό διάσπαση]], [[Johnson–Nyquist noise|θερμικό θόρυβο]], [[shot noiseΠυροβολισμός|θόρυβο πυροβολισμού]], και τον [[Noise (radio)Ραδιόφωνο|θόρυβο ραδιοφώνου]]. Ωστόσο, τα φυσικά φαινόμενα και τα εργαλεία που χρησιμοποιούνται για τη μέτρησή τους διαθέτουν γενικά ασυμμετρίες και συστηματικές αποκλίσεις που κάνουν τα αποτελέσματά τους να μην είναι ομοιόμορφα τυχαία. Μία [[randomnessΣυνάρτηση extractorπαραγωγής|συνάρτηση τυχαίας απαγωγής]], όπως μια [[cryptographic hashΣυνάρτηση functionκατατεμαχισμού|κρυπτογραφική συνάρτηση κατακερματισμού]], μπορεί να χρησιμοποιηθεί για να προσεγγίσει μια ομοιόμορφη κατανομή των δυαδικών ψηφίων από μία μη-ομοιόμορφα τυχαία πηγή, αν και σε χαμηλότερο ρυθμό δυαδικών ψηφίων.
Το 2010, ο Κάντερ et al. από το Πανεπιστήμιο του Μπαρ-Ιλάν, δημιούργησε μία φυσική γεννήτρια τυχαίων διαδικών ψηφίων που λειτουργεί σε ποσοστό 300 gigabits ανά δευτερόλεπτο, τη γρηγορότερη που έχει μέχρι στιγμής δημιουργηθεί.<ref>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).</ref>
=== Υπολογιστικές μεθόδοι ===
Οι γεννήτριες ψευδοτυχαίων αριθμών (PRNGs) είναι [[algorithmΑλγόριθμος|αλγόριθμοι]] που μπορούν να δημιουργήσουν αυτόματα μεγάλες σειρές αριθμών με καλές ιδιότητες τυχαιότητας, όμως η σειρά σε κάποιο σημείο αναγκάζεται να επαναληφθεί. Η σειρά των τιμών που παράγονται από τέτοιους αλγόριθμους καθορίζονται γενικά από ένα αρχικό αριθμό από ονομάζεται '''κλειδί''' ή '''σπορά'''. Ένας από τους πιο γνωστούς αλγόριθμους είναι η [[linear congruential generator|γραμμική συμβατική γεννήτρια]], η οποία χρησιμοποιεί την επανάληψη
:<math>X_{n+1} = (a X_n + b)\, \textrm{mod}\, m</math>
για να παράγει αριθμούς. Ο μέγιστος αριθμός των αριθμών του τύπου μπορεί να παράγει είναι o συντελεστής m . Για την αποφυγή ορισμένων μη τυχαίων ιδιοτήτων της γραμμικής συμβατικής γεννήτριας, αρκετές τέτοιες γεννήτριες με ελαφρώς διαφορετικές τιμές του συντελεστή πολλαπλασιασμού A μπορούν να χρησιμοποιηθούν παράλληλα με μια "κύρια" γεννήτρια τυχαίων αριθμών να επιλέγει μεταξύ των πολλών διαφορετικών γεννητριών.{{Citation needed|date=December 2013}}
Οι περισσότερες γλώσσες προγραμματισμού ηλεκτρονικών υπολογιστών συμπεριλαμβάνουν συναρτήσεις ή ρουτίνες σε βιβλιοθήκες που παρέχουν γεννήτριες τυχαίων αριθμών. Συχνά είναι σχεδιασμένες για να παρέχουν ένα τυχαίο byte, ένα τυχαίο ακέραιο αριθμό, ή έναν αριθμό κινητής υποδιαστολής που είναι ομοιόμορφα κατανεμημένος μεταξύ του 0 και 1.
Η ποιότητα των εν λόγω λειτουργιών ποικίλλουν ευρέως από εντελώς προβλέψιμη απόδοση, σε κρυπτογραφικά ασφαλές. Η βασική γεννήτρια τυχαίων αριθμών σε πολλές γλώσσες , συμπεριλαμβανομένης της [[Python_(programming_language)|Python]], [Ruby_(programming_language)|Ruby]], [[R_(programming_language)|R]] και [[PHP]] βασίζεται στον αλγόριθμο [[Mersenne Twister]] και '''δεν'' είναι επαρκής για κρυπτογραφικούς σκοπούς, όπως και αναφέρεται ρητά στην τεκμηρίωση της γλώσσας. Τέτοιες υλοποιήσεις έχουν συχνά κακές στατιστικές ιδιότητες και κάποιοιες επαναλαμβάνονται μετά από μόνο δέκα χιλιάδες δοκιμές . Συχνά αρχικοποιούνται χρησιμοποιώντας το ρολόι του χρόνου ενός υπολογιστή ως σπορά, αφού το ρολόι αυτό έχει [[Accuracy and precision|ακρίβεια]] χιλιοστών ενός δευτερολέπτου, κάτι αρκετά μεγαλύτερο από την ακρίβεια ενός ανθρώπου. Αυτές οι γεννήτριες είναι ικανοποιητικές για ορισμένες εργασίες (για παράδειγμα, βιντεοπαιχνίδια), αλλά είναι ακατάλληλα όπου απαιτείται τυχαιότητα υψηλής ποιότητας, όπως σε εφαρμογές κρυπτογραφίας, στατιστική ή αριθμητική ανάλυση.
Πολύ υψηλότερης ποιότητας πηγές τυχαίων αριθμών είναι διαθέσιμες για τα περισσότερα λειτουργικά συστήματα. Για παράδειγμα το [[/dev/random]] σε διάφορα συστήματα BSD, Linux, Mac OSX, IRIX και Solaris, ή [[CryptGenRandom]] για τα Microsoft Windows. Οι περισσότερες γλώσσες προγραμματισμού, συμπεριλαμβανομένων και των προαναφερθέντων, παρέχουν κάποια λειτουργικότητα που δίνει πρόσβαση σε αυτές τις πιο ποιοτικές πηγές.
=== Παραγωγή από κατανομή πιθανότητας ===
Υπάρχουν μερικές μέθοδοι που μπορούν να δημιουργήσουν έναν τυχαίο αριθμό με βάση μια [[probability density function|συνάρτηση πυκνότητας πιθανότητας]]. Αυτές οι μέθοδοι περιλαμβάνουν το μετασχηματισμό με κάποιο τρόπο ενός ομοιόμορφα τυχαίου αριθμού. Εξαιτίας αυτού, αυτές οι μέθοδοι λειτουργούν εξίσου καλά στην παραγωγή ψευδοτυχαίων και αληθινά τυχαίων αριθμών. Μία μέθοδος, που ονομάζεται η [[Inverse transform sampling|μέθοδος αναστροφής]], περιλαμβάνει την ενσωμάτωση επάνω σε μια περιοχή μεγαλύτερη ή ίση με τον τυχαίο αριθμό (η οποία θα πρέπει να παράγεται μεταξύ 0 και 1 για σωστές κατανομές). Μία δεύτερη μέθοδος, που ονομάζεται [[Rejection sampling|μέθοδος αποδοχής-απόρριψης]], περιλαμβάνει την επιλογή μιας τιμής x και y και ελέγχει αν η συνάρτηση του x είναι μεγαλύτερη από την τιμή y. Αν είναι, τότε η τιμή x είναι αποδεκτή. Διαφορετικά, η τιμή του x απορρίπτεται και ο αλγόριθμος προσπαθεί ξανά.<ref>{{cite web
| last = The MathWorks | first = | title = Common generation methods | date = | work = | url=http://www.mathworks.de/help/toolbox/stats/br5k9hi-1.html | accessdate = 2011-10-13 }}</ref><!-- [http://www.mathworks.com/access/helpdesk/help/toolbox/stats/bqttfc1.html#bqt8l8g]--><ref>{{ cite web | last = The Numerical Algorithms Group | first = | title = G05 – Random Number Generators | date = | work = NAG Library Manual, Mark 23 | url = http://www.nag.co.uk/numeric/fl/nagdoc_fl23/pdf/G05/g05intro.pdf | accessdate = 2012-02-09 }}</ref>
=== Παραγωγή από ανθρώπους ===
| 