The one-dimensional distribution of pseudo-random numbers generated by the ratio of uniforms methods using linear congruential generators (LCGs) as the source of uniform random numbers is investigated in this paper. Due to the two-dimensional lattice structure of LCGs there is always a comparable large gap without a point in the one-dimensional distribution of any ratio of uniforms method. Lower bounds for these probabilities only depending on the modulus and the Beyer quotient of the LCG are proved for the case that the Cauchy the normal or the exponential distribution are generated. These bounds justify the recommendation not to use the ratio of uniforms method combined with LCGs. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

To be effective, a linear congruential random number generator (LCG) should produce values that are (a) uniformly distributed on the unit interval (0,1) excluding endpoints and (b) substantially free of serial correlation. It has been found that many statistical methods produce inflated Type I error rates for correlated observations. Theoretically, independently seeding an LCG under the following conditions attenuates serial correlation: (a) simple random sampling of seeds, (b) non-replicate streams, (c) non-overlapping streams, and (d) non-adjoining streams. Accordingly, 4 algorithms (each satisfying at least 1 condition) were developed: (a) zero-leap, (b) fixed-leap, (c) scaled random-leap, and (d) unscaled random-leap. Note that the latter satisfied all 4 independent seeding conditions. To assess serial correlation, univariate and multivariate simulations were conducted at 3 equally spaced intervals for each algorithm (N=24) and measured using 3 randomness tests: (a) the serial correlation test, (b) the runs up test, and (c) the white noise test. A one-way balanced multivariate analysis of variance (MANOVA) was used to test 4 hypotheses: (a) omnibus, (b) contrast of unscaled vs. others, (c) contrast of scaled vs. others, and (d) contrast of fixed vs. others. The MANOVA assumptions of independence, normality, and homogeneity were satisfied. In sum, the seeding algorithms did not differ significantly from each other (omnibus hypothesis). For the contrast hypotheses, only the fixed-leap algorithm differed significantly from all other algorithms. Surprisingly, the scaled random-leap offered the least difference among the algorithms (theoretically this algorithm should have produced the second largest difference). Although not fully supported by the research design used in this study, it is thought that the unscaled random-leap algorithm is the best choice for independently seeding the multiplicative congruential random number generator. Accordingly, suggestions for further research are proposed.

Up to now all known efficient portable implementations of linear congruential random number generators with modulus 2^(31)-1 are working only with multipliers which are small compared with the modulus. We show that for non-uniform distributions, the rejection method may generate random numbers of bad quality if combined with a linear congruential generator with small multiplier. Therefore a method is described that works for any multiplier smaller than 2^(30). It uses the decomposition of multiplier and seed in high order and low order bits to compute the upper and the lower half of the product. The sum of the two halfs gives the product of multiplier and seed modulo 2^(31)-1. Coded in ANSI-C and FORTRAN77 the method results in a portable implementation of the linear congruential generator that is as fast or faster than other portable methods. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

Η ποιότητα πολλών εκ των αποτελεσμάτων της σύγχρονης έρευνας εξαρτώνται άμεσα από την «ποιότητα» και την ποσότητα των τυχαίων αριθμών που χρησιμοποιούνται. Ειδικότερα σε τομείς όπως η στοχαστική μοντελοποίηση και προσομοίωση προτιμώνται οι ντετερμινιστικές γεννήτριες τυχαίων αριθμών, ή αλλιώς γεννήτριες ψευδοτυχαίων αριθμών λόγω της δυνατότητας αναπαραγωγής των αποτελεσμάτων και της μεταφερσιμότητας τους. Επομένως, μας είναι χρήσιμο να εντοπίσουμε ψευδοτυχαίες γεννήτριες αριθμών με αυξημένη φαινόμενη τυχαιότητα αποτελεσμάτων. Για το λόγο αυτό, στη διπλωματική εργασία προτείνεται και εξετάζεται η καταλληλότητα της θραυσματικής διάστασης (fractal dimension) για την αξιολόγηση ψευδοτυχαίων γεννητριών τυχαίων αριθμών (Pseudorandom Number Generators). Η θραυσματική διάσταση αποτελεί μία μετρική που δύναται να εκφράσει την τυχαιότητα των αποτελεσμάτων μιας γεννήτριας ψευδοτυχαίων αριθμών καθώς «ποσοτικοποιεί» την κατανομή των ψευδοτυχαίων αριθμών στον ευκλείδειο χώρο. Σε πρώτο στάδιο γίνεται μία επισκόπηση των υπαρχουσών μεθοδολογιών παραγωγής τυχαίων αριθμών καθώς και των προσεγγίσεων για την αξιολόγηση της απόδοσης των ψευδοτυχαίων γεννητριών τυχαίων αριθμών. Οι καθιερωμένες τεχνικές που εφαρμόζονται για την αξιολόγηση μιας γεννήτριας εστιάζουν σε στατιστικά χαρακτηριστικά που έχουν ως στόχο να μετρήσουν πόσο απρόβλεπτα είναι τα αποτελέσματά της, ή χαρακτηριστικά όπως η περίοδος μιας γεννήτριας. Ακολούθως, μελετάται η θραυσματική διάσταση και οι προτεινόμενες στη βιβλιογραφία μέθοδοι υπολογισμού της. Στο στάδιο αυτό επιλέγεται η κατάλληλη μέθοδος για τον υπολογισμό της θραυσματικής διάστασης. Στο τελευταίο πειραματικό στάδιο παρουσιάζονται τα αποτελέσματα της μέτρησης της μορφοκλασματικής διάστασης. Οι ψευδοτυχαίες γεννήτριες προς αξιολόγηση που μετείχαν στα υπολογιστικά πειράματα ήταν η Γραμμική Αναλογική γεννήτρια, η γεννήτρια Blum-Blum-Shub, η γεννήτρια που βασίζεται στο κρυπτοσύστημα RSA και η γεννήτρια που βασίζεται στο πρόβλημα του διακριτού λογαρίθμου. Τα υπολογιστικά πειράματα επιχειρούν να ανακαλύψουν την απόδοση των εξεταζόμενων γεννητριών αλλά και την ευαισθησία της συμπεριφοράς τους ως προς τις παραμέτρους εισόδου των γεννητριών. / Scientific experimental results are highly dependent on the "quality" and quantity of random numbers used for these experiments. Especially in areas such as stochastic modeling and simulation, deterministic random number generators, known as pseudorandom number generators are preferred because of reproducibility of the results and their portability. Trying to identify pseudorandom number generators sequences which appear to be random, we examine the suitability of Fractal Dimension measurement for assessing Pseudorandom Number Generators. The established techniques that are used to evaluate a generator are focused on statistical features that are designed to detect correlations into generated pseudorandom number sequences. On the other hand, Fractal Dimension is a metric that can express the randomness of the results of a pseudorandom number generator as it "quantifies" the distribution of pseudorandom numbers in Euclidean space. We attempt to evaluate some Pseudorandom Number Generators, like classical Linear Congruential generator, Blum-Blum-Shub generator, the generator based on RSA cryptosystem and the generator based on the Discrete Logarithm problem. The computational experiments presented in our work attempt to assess the performance and the sensitivity of the examined generators.