Το προφίλ μας στο Google Plus
2

Τυχαίοι αριθμοί, μέρος 2/2: Γεννήτριες τυχαιότητας

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

Τυχαίοι αριθμοί, μέρος 2/2: Γεννήτριες τυχαιότητας

Φανταστείτε έναν περίπλοκο μηχανισμό, ο οποίος λειτουργεί με συγκεκριμένο και γνωστό τρόπο. Ασχέτως του πλήθους των γραναζιών και των ελατηρίων που τον απαρτίζουν, η κατάστασή του είναι πάντοτε προβλέψιμη. Μπορεί να απαιτούνται αρκετοί και σύνθετοι υπολογισμοί, όπως επίσης και καλή γνώση της αρχικής κατάστασης του μηχανισμού, αλλά τουλάχιστον μπορούμε να είμαστε σίγουροι για την πρόβλεψή μας. Κάτι αντίστοιχο ισχύει και για τις συναρτήσεις που παράγουν ψευδοτυχαίους αριθμούς. Μπορεί ο μηχανισμός τους να είναι περίπλοκος, αλλά η συμπεριφορά τους είναι πάντοτε προβλέψιμη. Ακριβώς γι’ αυτό, μια τέτοια “πηγή” αριθμών χαρακτηρίζεται κι ως ντετερμινιστική (deterministic). Φανταστείτε τώρα ένα φυσικό φαινόμενο, το οποίο είτε δεν έχουμε καταφέρει να ερμηνεύσουμε ακόμα, είτε μας είναι δύσκολο να μοντελοποιήσουμε. Ένα τέτοιο φαινόμενο θα μπορούσε να χρησιμεύσει για την παραγωγή αριθμών που είναι αδύνατο να προβλέψουμε κι ως εκ τούτου μπορούμε να τους θεωρούμε *πραγματικά* τυχαίους. Μία τέτοια πηγή αριθμών ονομάζεται μη-ντετερμινιστική (non-deterministic). Σε αυτό το άρθρο θα εξετάσουμε ένα αντιπροσωπευτικό δείγμα από το κάθε είδος.

Γεννήτριες ψευδοτυχαίων αριθμών
Εδώ ανήκουν οι αλγόριθμοι που παράγουν δύσκολα προβλέψιμες αλληλουχίες αριθμών. Βέβαια, οι αλγόριθμοι αυτής της κατηγορίας είναι περισσότερο γνωστοί με το αγγλικό τους όνομα: Pseudo Random Number Generator ή, πιο σύντομα, PRNG. Σε αυτούς τους μηχανισμούς δίνουμε μια τιμή που ονομάζεται seed (σπόρος) κι αυτοί με τη σειρά τους επιστρέφουν μια αλληλουχία ψευδοτυχαίων αριθμών. Αυτό που αξίζει να σημειώσουμε, είναι ότι αν δώσουμε τον ίδιο “σπόρο”, θα πάρουμε την ίδια ακριβώς αλληλουχία αριθμών. Συνεπώς, οι εν λόγω αλγόριθμοι μπορούν να δημιουργήσουν τόσες διαφορετικές αλληλουχίες αριθμών, όσες είναι και οι διαφορετικές τιμές που μπορούν να δεχτούν στην είσοδό τους. Κατά παράδοση, το μέγεθος που δίνεται σαν seed σε αυτούς τους αλγόριθμους είναι η τιμή του system clock. Βλέπετε, το συγκεκριμένο “ρολόι” έχει πολύ μεγάλη ακρίβεια και κάθε φορά που το “διαβάζουμε” είναι σχεδόν σίγουρο ότι θα μας δώσει μια διαφορετική τιμή.

Παρακάτω βλέπουμε ένα μικρό πρόγραμμα σε C, το οποίο αξιοποιεί έναν μετρητή υψηλής ακρίβειας (high resolution timer) για να μας δώσει ένα seed. Το πρόγραμμα είναι γραμμένο για την πλατφόρμα των Windows και μετράει το χρόνο εκτέλεσης της συνάρτησης sleep(), για μια συγκεκριμένη παράμετρο. Επειδή η εν λόγω συνάρτηση δεν είναι ιδιαίτερα ακριβής στα Windows, ενώ αντίθετα ο μετρητής που χρησιμοποιούμε έχει τεράστια ακρίβεια, το αποτέλεσμα που λαμβάνουμε είναι πολύ συχνά διαφορετικό…

Διαβάστε ολόκληρο το άρθρο στο deltaHacker 031 (τεύχος Απριλίου 2014).

Το μηνιαίο περιοδικό deltaHacker είναι αποκλειστικά ψηφιακό (μορφή PDF). Μάθετε για τις απίστευτες τιμές των συνδρομών αλλά και για τα εκτενή κι αναλυτικά video tutorials (deltaCast), και κάντε τώρα την παραγγελία σας από τη σχετική φόρμα. Προσοχή: Για την πλήρη πρόσβαση στο deltaCast απαιτείται ενεργή συνδρομή στο περιοδικό.

2 Responses to “Τυχαίοι αριθμοί, μέρος 2/2: Γεννήτριες τυχαιότητας”

  1. Captain_Harlock | 08/06/2014 at 19:12

    Σε ένα post που έχει αναρτηθεί στο forum του raspberry pi αναφέρεται ότι έχουν κάνει modify το latest firmware με αποτέλεσμα να εμπεριέχει ένα hardware random number generator module! Η παραγωγή πραγματικά τυχαίων αρίθμων γίνεται μέσω του chipset 2835 που χρησιμοποιείται για HD processing από την συσκευή. To device το οποίο παράγει τους real random numbers είναι το “/dev/hwrng”.
    Για να το τρέξετε δοκιμάστε τα εξής:

    sudo modprobe bcm2708-rng
    sudo apt-get install rng-tools
    sudo cat /dev/hwrng | rngtest -c 1000

    Πηγή:
    http://www.raspberrypi.org/forums/viewtopic.php?f=29&t=19334&p=273944#p273944

  2. george.aravidis | 08/06/2014 at 20:08

    Ενδιαφέρον αγαπητέ Captain_Harlock. Όπως διάβασα και στα σχόλια, το chip 2835 περιέχει entropy source! Πραγματικά ενδιαφέρον! Ευχαριστούμε !!

Leave a Reply

You must be logged in to post a comment.

Σύνδεση

Αρχείο δημοσιεύσεων