Subroutines are written to generate random numbers on the computer. Depending on the subroutine used, the generated random numbers follow the uniform, binomial, normal, chi-square, t, F, or gamma distribution. Each subroutine is tested using the chi-square goodness of fit test to verify that the random numbers generated by each subroutine follow the statistical distribution for which it is written. The interpretation of the test results indicates that each subroutine generates random numbers which closely approximates the theoretical distribution for which it is designed. The approach used in the subroutine which generates gamma distributed random numbers involves the use of numerical integration, whereas simpler techniques are used in all the other subroutines. Each subroutine is documented with a description of how to use it and an explanation of the methods used to obtain the random numbers which it is designed to generate. (77 pages)

Random Numbers form the heart and soul of a discrete-event simulation system. There are few situations where the actions of the entities in the process being simulated can be completely predicted in advance. The real world processes are more probabilistic than deterministic. Hence, such chances are represented in the system by using various statistical models, like random number generators. These random number generators can be used to represent a various number of factors, such as length of the queue. However, simulations have grown in size and are sometimes required to run on multiple machines, which share the various methods or events in the simulation among themselves. These Machines can be distributed across a LAN or even the internet. In such cases, to keep the validity of the simulation model, we need rollback-able random number generators. This thesis is an effort to develop such rollback able random number generators for the Synchronous Parallel Environment for Emulation and Discrete-Event Simulation (SPEEDES) environment developed by NASA. These rollback-able random number generators will also add several statistical distribution models to the already rich SPEEDES library.

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

A robust simulation-based optimization approach is proposed for truck-shovel systems in surface coal mines to maximize the expected value of revenue obtained from loading customer trains. To this end, a large surface coal mine in North America is considered as case study. A data-driven modeling framework is developed and then applied to automatically generate a highly detailed simulation model of the mine in Arena. The framework comprises a formal information model based on Unified Modeling Language (UML), which is used to input mine structural as well as production information. Petri net-based model generation procedures are applied to automatically generate the simulation model based on the whole set of simulation inputs. Then, factors encountered in material handling operations that may affect the robustness of revenue are then classified into 1) controllable; and 2) uncontrollable categories. While controllable factors are trucks locked to routes, uncontrollable factors are inverses of summation over truck haul, and shovel loading and truck-dumping times for each route. Historical production data of the mine contained in a data warehouse is used to derive probability distributions for the uncontrollable factors. The data warehouse is implemented in Microsoft SQL, and contains snapshots of historical equipment statuses and production outputs taken at regular intervals in each shift of the mine. Response Surface Methodology is applied to derive an expression for the variance of revenue as a function of controllable and uncontrollable factors. More specifically, 1) first order and second order effects for controllable factors, 2) first order effects for uncontrollable factors, and 3) two factor interactions for controllable and uncontrollable factors are considered. Latin Hypercube Sampling method is applied for setting controllable factors and the means of uncontrollable factors. Also, Common Random Numbers method is applied to generate the sequence of pseudo-random numbers for uncontrollable factors in simulation experiments for variance reduction between different design points of the metamodel. The variance of the metamodel is validated using leave-one-out cross validation. It is later applied as an additional constraint to the mathematical formulation to maximize revenue in the simulation model using OptQuest. The decision variables in this formulation are truck locks only. Revenue is a function of the actual quality of coal delivered to each customer and their corresponding quality specifications for premiums and penalties. OptQuest is an optimization add-on for Arena that uses Tabu search and Scatter search algorithms to arrive at the optimal solution. The upper bound on the variance as a constraint is varied to obtain different sets of expected value as well as variance of optimal revenue. After comparison with results using OptQuest with random sampling and without variance expression of metamodel, it has been shown that the proposed approach can be applied to obtain the decision variable set that not only results in a higher expected value but also a narrower confidence interval for optimum revenue. According to the best of our knowledge, there are two major contributions from this research: 1) It is theoretically demonstrated using 2-point and orthonormal k-point response surfaces that Common Random Numbers reduces the error in estimation of variance of metamodel of simulation model. 2) A data-driven modeling and simulation framework has been proposed for automatically generating discrete-event simulation model of large surface coal mines to reduce modeling time, expenditure, as well as human errors associated with manual development.

Cette thèse adresse le sujet de la génération de suites binaires aléatoires dans les circuits logiques programmables FPGA et plus particulièrement les suites dont l’origine aléatoire est de nature physique et non algorithmique. De telles suites trouvent une utilisation abondante dans la plupart des protocoles cryptographiques. Un état de l’art portant sur les différentes méthodes de génération de vrai aléa dans les circuits logiques programmables est présenté sous forme d’analyse critique d’articles scientifiques. Une synthèse des différentes tendances dans l’extraction et la génération d’aléa est également présentée. Une campagne d’expériences et de mesures est présentée visant à caractériser les différentes sources de signaux aléatoires disponibles à l’intérieur du FPGA. Des phénomènes intéressants tel le verrouillage de plusieurs oscillateurs en anneau, la dépendance de la source d’aléa vis-à-vis de la logique environnante et la méthodologie de mesure du jitter sont analysés. Plusieurs méthodes nouvelles de génération de suites binaires aléatoires sont décrites. Finalement une méthodologie nouvelle de simulation en VHDL de générateurs complets ainsi qu’un modèle mathématique d’un oscillateur en anneau en tant que source d’aléa sont présentés / This thesis addresses the topic of the generation of random binary streams in FPGA and especially random sequences whose origin is physical and not algorithmic. Such sequences find abundant use in most cryptographic protocols. A state of the art regarding the various methods of generating true randomness in programmable logic is presented as a critical analysis of scientific articles. A synthesis of different trends in the extraction and generation of true randomness is presented. A campaign of experiments and measurements is presented to characterize the different sources of random signals available inside the FPGA. Interesting phenomena such as the locking of several ring oscillators and the sensibility of the source of randomness depending to the surrounding logic activity are reported. Several new methods for generating random binary sequences are described and analyzed. Finally a new simulation methodology in VHDL and a mathematical model of a ring oscillator as a source of randomness for TRNG are presented

En verkstad som tillverkar växellådor planerade att bygga om verkstaden. Det fanns flera problem i verkstaden som indirekt påverkade produktionen. Att tåg stod stilla utan att göra ett aktivt arbete på en huvudled i verkstaden sågs som ett stort problem. Ett annat problem var att det fanns för många tåg i verkstaden. Den planerade ombyggnationen var till för att få ned antalet tåg i verkstaden. Med ombyggnationen ville verkstadens ansvariga undersöka ytterligare möjligheter hur verkstaden skulle kunna förändras och kunna lösa delar av problemen. Det var även intressant att se om möjliga implementeringar av verkstaden skulle ge en ökad produktion. Målen var att skapa ett simuleringsverktyg för att undersöka hur olika lösningar som baserades på ombyggnationen skulle kunna påverka ett tåg som fyllde på material till monteringslinor i verkstaden. För att kunna testa olika lösningar behövde en simuleringsmodell utvecklas och verifieras mot den befintliga lösningen i verkstaden. Därefter utökades modellen för att testa nya lösningar. Från verkstaden fanns det data på konsumering av material. För tåget som skulle fylla på material fanns det teoretiska tider för olika arbetsmoment. Konsumeringen av material uppförde sig enligt en slumpfördelning som var normalfördelad. Resultatet blev att endast konsumeringen av material kunde verifieras då det bara fanns data på hur konsumtionen av material skedde. Resterande delar av simuleringen använde teoretiska planerade värden. Av de undersökta lösningarna var det en lösning med en ny hållplats på en mindre trafikerad väg, där ett tåg kunde vänta, som visade ett mer önskat resultat än de andra som undersöktes. / A workshop that produces gearboxes planned to remodel the workshop. There were several problems that indirectly affected the production. The fact that trains stood still without doing active work on the main road in the workshop was a major problem. Another problem was that there were too many trains in the workshop. The planned reconstruction was to reduce the number of trains in the workshop. With the remodel, those responsible for the workshop wanted to explore further possibilities on how the workshop could be changed. It was also interesting to see if the implementation of changes would give an increased production. The goals were to create a simulation tool to investigate how different solutions based on the rebuild could affect a train that loaded the material into assembly lines in the workshop. To be able to test different solutions, a simulation model needed to be developed and verified against the existing solution. Then the model was expanded to test new solutions. From the workshop there was data on the consumption of materials. For the train that would load up on materials, there were theoretical times for various work tasks. The consumption of materials behaved according to a random distribution that was normally distributed. The result was that only the consumption of materials could be verified as there was only data on how the consumption of materials took place. Remaining parts of the simulation used theoretically planned values. Of the solutions investigated, it was a solution with a new bus stop on a less busy road, where a train could wait, that showed a more desirable result than the others that were investigated.

Les générateurs de nombres véritablement aléatoires (TRNG) sont des composants cruciaux dans certaines applications cryptographiques sensibles (génération de clés de chiffrement, génération de signatures DSA, etc). Comme il s’agit de composants très bas-niveau, une faille dans le TRNG peut remettre en question la sécurité de tout le système cryptographique qui l’exploite. Alors que beaucoup de principes de TRNG existent dans la littérature, peu de travaux analysent rigoureusement ces architectures en termes de sécurité. L’objectif de cette thèse était d’étudier les avantages des techniques de conception asynchrone pour la conception de générateurs de nombres véritablement aléatoires (TRNG) sûrs et robustes. Nous nous sommes en particulier intéressés à des oscillateurs numériques appelés anneaux auto-séquencés. Ceux-ci exploitent un protocole de requêtes et acquittements pour séquencer les données qui y circulent. En exploitant les propriétés uniques de ces anneaux, nous proposons un nouveau principe de TRNG, avec une étude théorique détaillée sur son fonctionnement, et une évaluation du cœur du générateur dans des cibles ASIC et FPGA. Nous montrons que ce nouveau principe permet non seulement de générer des suites aléatoires de très bonne qualité et avec un très haut débit (>100 Mbit/s), mais il permet aussi une modélisation réaliste de l’entropie des bits de sortie (celle-ci peut être réglée grâce aux paramètres de l’extracteur). Ce travail propose également une méthodologie complète pour concevoir ce générateur, pour le dimensionner en fonction du niveau de bruit dans le circuit, et pour le sécuriser face aux attaques et défaillances / True Random Number Generators (TRNG) are ubiquitous in many critical cryptographic applications (key generation, DSA signatures, etc). While many TRNG designs exist in literature, only a few of them deal with security aspects, which is surprising considering that they are low-level primitives in a cryptographic system (a weak TRNG can jeopardize a whole cryptographic system). The objective of this thesis was to study the advantages of asynchronous design techniques in order to build true random number generators that are secure and robust. We especially focused on digital oscillators called self-timed rings (STR), which use a handshake request and acknowledgement protocol to organize the propagation of data. Using some of the unique properties of STRs, we propose a new TRNG principle, with a detailed theoretical study of its behavior, and an evaluation of the TRNG core in ASICs and FPGAs. We demonstrate that this new principle allows to generate high quality random bit sequences with a very high throughput (> 100 Mbit/s). Moreover, it enables a realistic estimation for the entropy per output bit (this entropy level can be tuned using the entropy extractor parameters). We also present a complete methodology to design the TRNG, to properly set up the architecture with regards to the level of noise in the circuit, and to secure it against attacks and failures

Orientador: Prof. Dr. Vinicius Cifú Lopes / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015. / Este trabalho apresenta brevemente o conceito de aleatoriedade e de sequência de números aleatórios. Em especial são apresentados alguns exemplos de problemas que podem ser resolvidos utilizando "bons" números aleatórios associados a algoritmos computacionais. Também é explicada a diferença entre números verdadeiramente aleatórios e pseudoaleatórios. São introduzidos alguns métodos básicos de geração de números pseudoaleatórios, envolvendo alguns conceitos matemáticos, principalmente teoria elementar dos números. Em seguida são mencionados alguns testes de qualidade e métodos de transformação de variáveis. Ao final é apresentada uma sugestão de atividade para o ensino médio. / This thesis briefly presents the concepts of randomness and random numbers sequence. More specifically, we discuss a few examples of problems which can be solved using the concept of "good" random numbers, associated to computational algorithms. We mention as well the difference between true random numbers and pseudo random numbers. Then we introduce a number of basic methods to generate pseudo random numbers, in which we discuss the related mathematical concepts, mainly from elementary numbers theory. A presentation follows, of some quality tests applicable to the theory, and methods of variable transformation. We close with a suggestion of how to use those concepts in an activity targeting high school students.

Im Kern der vorliegenden Arbeit wird eine neue Vorfahrtstrategie zur Steuerung von Materialflüssen an Zusammenführungen vorgestellt. Das Hauptanwendungsgebiet stellen innerbetriebliche Transportsysteme dar, wobei die Erkenntnisse auf beliebige Transport- bzw. Bediensysteme übertragbar sind. Die Arbeit grenzt sich mit der Annahme autokorrelierter Ankunftsprozesse von bisheriger Forschung und Entwicklung ab. Bis dato werden stets unkorrelierte Ströme angenommen bzw. findet keine spezielle Beachtung autokorrelierter Ströme bei der Vorfahrtsteuerung statt. Untersuchungen zeigen aber, dass zum einen mit hoher Konfidenz mit autokorrelierten Materialflüssen zu rechnen ist und in diesem Fall zum anderen von einem erheblichen Einfluss auf die Systemleistung ausgegangen werden muss. Zusammengefasst konnten im Rahmen der vorliegenden Arbeit 68 Realdatensätze verschiedener Unternehmen untersucht werden, mit dem Ergebnis, dass ca. 95% der Materialflüsse Autokorrelation aufweisen. Ferner wird hergeleitet, dass Autokorrelation intrinsisch in Materialflusssystemen entsteht. Die Folgen autokorrelierter Prozesse bestehen dabei in längeren Durchlaufzeiten, einem volatileren Systemverhalten und höheren Wahrscheinlichkeiten von Systemblockaden. Um die genannten Effekte an Zusammenführungen zu eliminieren, stellt die Arbeit eine neue Vorfahrtstrategie HAFI – Highest Autocorrelated First vor. Diese priorisiert die Ankunftsprozesse anhand deren Autokorrelation. Konkret wird die Vorfahrt zunächst so lange nach dem Prinzip First Come First Served gewährt, bis richtungsweise eine spezifische Warteschlangenlänge überschritten wird. Der jeweilige Wert ergibt sich aus der Höhe der Autokorrelation der Ankunftsprozesse. Vorfahrt bekommt der Strom mit der höchsten Überschreitung seines Grenzwertes. Die Arbeit stellt ferner eine Heuristik DyDeT zur automatischen Bestimmung und dynamischen Anpassung der Grenzwerte vor. Mit einer Simulationsstudie wird gezeigt, dass HAFI mit Anwendung von DyDeT die Vorzüge der etablierten Vorfahrtstrategien First Come First Served und Longest Queue First vereint. Dabei wird auch deutlich, dass die zwei letztgenannten Strategien den besonderen Herausforderungen autokorrelierter Ankunftsprozesse nicht gerecht werden. Bei einer Anwendung von HAFI zur Vorfahrtsteuerung können Durchlaufzeiten und Warteschlangenlängen auf dem Niveau von First Come First Served erreicht werden, wobei dieses ca. 10% unter dem von Longest Queue First liegt. Gleichzeitig ermöglicht HAFI, im Gegensatz zu First Come First Served, eine ähnlich gute Lastbalancierung wie Longest Queue First. Die Ergebnisse stellen sich robust gegenüber Änderungen der Auslastung sowie der Höhe der Autokorrelation dar. Gleichzeitig sind die Erkenntnisse unabhängig der Analyse einer isolierten Zusammenführung und der Anordnung mehrerer Zusammenführungen in einem Netzwerk. / The work at hand presents a novel strategy to control arrival processes at merges. The main fields of application are intralogistics transport systems. Nevertheless, the findings can be adapted to any queuing system. In contrast to further research and development the thesis assumes autocorrelated arrival processes. Up until now, arrivals are usually assumed to be uncorrelated and there are no special treatments for autocorrelated arrivals in the context of merge controlling. However, surveys show with high reliability the existence of autocorrelated arrivals, resulting in some major impacts on the systems\' performance. In detail, 68 real-world datasets of different companies have been tested in the scope of this work, and in 95% of the cases arrival processes significantly show autocorrelations. Furthermore, the research shows that autocorrelation comes from the system itself. As a direct consequence it was observed that there were longer cycle times, more volatile system behavior, and a higher likelihood of deadlocks. In order to eliminate these effects at merges, this thesis introduces a new priority rule called HAFI-Highest Autocorrelated First. It assesses the arrivals\' priority in accordance to their autocorrelation. More concretely, priority initially is given in accordance to the First Come First Served scheme as long as specific direction-wise queue lengths are not exceeded. The particular thresholds are determined by the arrival processes\' autocorrelation, wherein the process with the highest volume gets priority. Furthermore, the thesis introduces a heuristic to automatically and dynamically determine the specific thresholds of HAFI-so called DyDeT. With a simulation study it can be shown that HAFI in connection with DyDeT, combines the advantages of the well-established priority rules First Come First Served and Longest Queue First. It also becomes obvious that the latter ones are not able to deal with the challenges of autocorrelated arrival processes. By applying HAFI cycling times and mean queue lengths on the level of First Come First Served can be achieved. These are about 10% lower than for Longest Queue First. Concomitantly and in contrast to First Come First Served, HAFI also shows well balanced queues like Longest Queue First. The results are robust against different levels of throughput and autocorrelation, respectively. Furthermore, the findings are independent from analyzing a single instance of a merge or several merges in a network.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-07-11T13:06:08Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TeseJoseversaoCD.pdf: 2349040 bytes, checksum: f9cf2bfb304c798e864da4edd16e3a90 (MD5) / Made available in DSpace on 2017-07-11T13:06:08Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) TeseJoseversaoCD.pdf: 2349040 bytes, checksum: f9cf2bfb304c798e864da4edd16e3a90 (MD5) Previous issue date: 2016-02-26 / CNPQ / Geradores de números pseudo-aleatórios são amplamente utilizados em aplicações científicas e tecnológicas. Particularmente em criptografia, estes são empregados em sistemas de chave secreta, como geradores de sequências de cifragem. Neste trabalho, propomos algumas metodologias para o projeto destes geradores a partir de mapas caóticos. A primeira é baseada em duas técnicas: salto de amostras e discretização codificada variante no tempo. Mostra-se que o procedimento possui alta taxa de geração de bits por amostra caótica quando comparado com a codificação fixa no tempo, além de dispensar pós-processamento para melhoria de suas propriedades aleatórias. A outra metodologia utilizada é o emprego de sequências-m para eliminar a correlação residual na sequência codificada. A discretização variante no tempo apresenta uma característica de correlação bem definida que é aproveitada por um novo bloco de pós-processamento que utiliza sequências-m de menor complexidade linear que a metodologia anterior. Validam-se os métodos propostos empregando a bateria de teste NIST. / Random number generators are widely used in scientific and technological applications. Particularly in cryptography, they are used in secret-key systems, such as key sequence generators. In this work, we present two methodologies for the design of these generators from chaotic maps. The first one is based on two techniques: Skipping and time-varying coded discretization. We show that the proposed method has higher bit generation rate when compared to fixed-time coded discretization and dispenses post-processing in order to improve their random properties. Another methodology is the use of m-sequences to eliminate the residual correlation of the coded sequence. The time-varying coded discretization has a well-defined correlation characteristic that is exploited by a new block ofpost-processing using m-sequences that requires less memory than the previous methodology. The effectiveness of this procedure is verified through the NIST test.