Particle transport Monte Carlo simulations are a key tool for High Energy Physics experiments, including the LHC experiments at CERN. All Monte Carlo (MC) simulations depend vitally on Pseudo-Random Number Generators (PRNGs) used to sample many distributions. Each LHC experiments generates 5-10 Billion sampled physics events a year using around 10^18 sampled values from PRNGs. PRNGs take 1-5% of CPU time. PRNGs used must possess very large periods, fast execution, the ability to create a large number of streams, and very good correlation properties between streams and sampled values. It must be possible to reproduce a simulated event any time, for reexamination or debugging. The transition from event-level parallelism in Geant4 to dynamical multithreading in GeantV requires associating the random generator states not with the threads but with the tracks, which are shuffled between "baskets" based on their type and energy. Maintaining reproducibility after such transition requires a drastic change in the way the random generators are used. We suggest solutions based on Scalable Pseudo Random Number Generators and on pedigrees introduced in CilkPlus, which are first tested in Geant4.