N.I. Chervyakov, M.G. Babenko, N.F. Semenova

This paper proposes a method for finding irreducible polynomials for the construction of pseudo-random numbers, we use an irreducible polynomial of degree over the prime field ,, which lies at the heart of the cryptosystem XTR. A new algorithm of the random number generator based cryptosystem XTR, all operations are performed with the numbers in the system of residual classes, and problems in the system of residual classes with the use of an approximate method. As a result of computer simulation developed for pseudorandom numbers over the fields of dimension 521 will benefit from the speed of the algorithm for pseudo-random number that is constructed with a cryptosystem XTR, calculations which are made in the system of residual classes, is 140% on the method, where the computation is done in a positional notation.