Study of Algorithms for Primitive Polynomials

this report we shall present the fundamentals of random number generation on parallel processors. We shall exhibit how the practical task of carrying out stochastic simulation on a parallel machine leads deeply into number theory and algebra. We shall see that some classical algorithms which have proved to be excellent for single-processor machines, are either useless or require greatest care in the case of parallel processors. Stochastic simulation is one of the important tasks for single- as well as multiprocessor machines. Computer simulations of real-life processes based on stochastic models have become one of the most interesting -- and demanding -- applications of mathematics. Due to the computational complexity of the problems, parallelization of the underlying algorithms is receiving increasing attention. As a basic condition to any research, we should be able to reproduce and to verify a scientific experiment. These two requirements and, further, considerations of storage and computational effectiveness rule out physical sources for random numbers, such as radioactive decay or electronic noise. The efficient generation of random numbers of high statistical quality is an absolute necessity for stochastic simulation. In his well-known monograph, Ripley [19, p.2] writes: "The first thing needed for a stochastic simulation is a source of randomness. This is often taken for granted but is of fundamental importance. Regrettably many of the so-called random functions supplied with the most widespread computers are far from random, and many simulation studies have been invalidated as a consequence." D5H-1/Rel 1.0/April 27, 1994 Random number generators for parallel processors PACT The following statement from Ripley[19, p.14] does not exaggerate the actual situation:..