Randomness properties of some vector sequences generated by multivariate polynomial iterations

Download

index.pdf

Date

2016

Author

Gürkan Balıkçıoğlu, Pınar

Metadata

Show full item record

Item Usage Stats

39
views

21
downloads

We examine the randomness properties of the sequences generated by the multivariate polynomial iterations method proposed by Ostafe and Shparlinski, by using the six different choices of polynomials given by the same authors. Our analysis is based on two approaches: distributions of the periods and linear complexities of the produced vector sequences. We deﬁne the efﬁciency parameters, PE for “period efﬁciency” and LCE for “linear complexity efﬁciency”, so that the actual values of the period and linear complexity of a sequence can be easily compared with those of the ideal cases. For each polynomial choice, in order to obtain the period distribution of the generated vector sequences, we perform an exhaustive search for prime ﬁeld sizes up to 13; and observe that the probability of attaining a maximum-period sequence is extremely low. Linear complexities of the sequences are also computed exhaustively for prime ﬁeld sizes up to 13 and the multivariate polynomial iterations with the proposed polynomial choices are observed to generate sequences with having high linear complexities quite seldomly. We then concentrate on the largest period sequences produced by each choice, and investigate the linear complexity of those sequences for a given polynomial choice, at a speciﬁc ﬁeld size p and number of polynomials m. We observe that an increase of p or m does not bring any improvement on the randomness of the generated sequences. Finally, we analyze the linear complexity of Ostafe’s sequences by ﬁxing the period but leaving the choice of m and other initial values random,as in real life. Although computational constraints limit our exhaustive search results in the ﬁrst part to relatively small values of p and m; the last part of our study lets us use higher values of p and m, to justify the projection that Ostafe’s method with the proposed polynomial choices is not a promising way of implementing pseudo-random number generators.

Subject Keywords

Polynomials., Mathematical statistics., Iterative methods (Mathematics).

URI

http://etd.lib.metu.edu.tr/upload/12619823/index.pdf
https://hdl.handle.net/11511/25512

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Betti Numbers of Smooth Schubert Varieties and the Remarkable Formula of Kostant, Macdonald, Shapiro, and Steinberg Akyıldız, Ersan (2012-01-01) The purpose of this note is to give a refinement of the product formula proved in [1] for the Poincare polynomial of a smooth Schubert variety in the flag variety of an algebraic group G over C. This yields a factorization of the number of elements in a Bruhat interval [e,w] in the Weyl group W of G provided the Schubert variety associated to w is smooth. This gives an elementary necessary condition for a Schubert variety in the flag variety to be smooth.
Calculations of the roots of classical orthogonal polynomials: an application to gaussian quadrature Shaidolda, Gulnaz; Taşeli, Hasan; Department of Mathematics (2019) This thesis focuses on classical orthogonal polynomials namely Jacobi, Laguerre and Hermite polynomials and a method to calculate the roots of these polynomials is constructed. The roots are expressed as the eigenvalues of a tridiagonal matrix whose coefficients depend on the recurrence formula for the classical orthogonal polynomials. These approximations of roots are used as method of computation of Gaussian quadratures. Then the discussion of the numerical results are then introduced to deduce the effici...
Global existence and boundedness for a class of second-order nonlinear differential equations Tiryaki, Aydin; Zafer, Ağacık (Elsevier BV, 2013-09-01) In this paper we obtain new conditions for the global existence and boundedness of solutions for nonlinear second-order equations of the form
HFE based multi-variate quadratic cryptosystems and Dembowski Ostrom polynomials Alam, Bilal; Akyıldız, Ersan; Kırlar, Barış Bülent; Department of Cryptography (2013) Harayama and Friesen proposed linearised binomial attack for multivariate quadratic cryptosystems and introduced weak Dembowski Ostrom(DO) polynomials in this framework over the finite fi eld F2. They conjecture about the existence of infi nite class of weak DO polynomials and presented the open problem of enumerating their classes. We extend linearised binomial attack to multivariate quadratic cryptosystems over Fp for any prime p and redefi ne the weak DO polynomials for general case. We identify an in fi...
Noncomplex smooth 4-manifolds with Lefschetz fibrations Korkmaz, Mustafa (2001-01-01) For every integer g ≥ 2 there exist infinitely many pairwise nonhomeomorphic smooth 4-manifolds admitting genus-g Lefschetz fibration over S2 but not carrying any complex structure. This extends a recent result of Ozbagci and Stipsicz.

Citation Formats

P. Gürkan Balıkçıoğlu, “Randomness properties of some vector sequences generated by multivariate polynomial iterations,” Ph.D. - Doctoral Program, Middle East Technical University, 2016.