Randomness properties of some vector sequences generated by multivariate polynomial iterations

Abstract

Ostafe ve Shparlinski tarafından önerilen çok değişkenli polinom iterasyonları ile üretilendizilerin, aynı yazarlar tarafından önerilen altı polinom seçeneği için rassallık özellikleriniaraştırdık. Analizimiz iki yaklaşımı temel almaktadır: üretilen vektör dizilerininperiyot ve doğrusal karmaşıklık dağılımı. Elde ettiğimiz değerleri, bu yaklaşımlarınideal durumları ile karşılaştırabilmek amacıyla, periyot yeterliliği için PE ve doğrusalkarmaşıklık yeterliği için LCE olmak üzere, yeterlik parametreleri tanımladık. Üretilenvektör dizilerinin, her bir polinom seçeneği için periyot dağılımını elde edebilmekamacıyla, büyüklüğü 13'e kadar olan asal alanlar için tüm olası durumlar üzerindenaraştırma yaptık ve maksimum uzunluklu dizilere erişme olasılığının oldukça düşükolduğunu gözlemledik. Ayrıca büyüklüğü 13'e kadar olan asal alanlar için tüm olasıdurumlar üzerinden dizilerin doğrusal karmaşıklıklarını araştırdık ve çok değişkenlipolinom iterasyonları metoduyla birlikte önerilen polinom seçimlerinin, oldukça seyrekdurumlarda yüksek doğrusal karmaşıklığa sahip diziler üretebildiğini gözlemledik. Ardından,her seçim tarafından üretilen en yüksek periyotlu dizilere yoğunlaştık ve budizilerin verilen bir seçim için, belirli bir alan büyüklüğü (p) ve polinom sayısındaki(m) doğrusal karmaşıklığını inceledik. p ve m'yi arttırmanın üretilen dizilerin rassallığına dair herhangi bir iyileşme sağlamadığını gözlemledik. Son olarak, gerçekhayattaki gibi periyotları sabit tutup, m ve diğer başlangıç değerlerini rassal olarakalıp; Ostafe'nin dizilerinin doğrusal karmaşıklığını analiz ettik. İlk bölümdeki kapsamlıaraştırmamızı hesaplama zorlukları nedeniyle nispeten küçük p ve m değerleriile sınırlamamıza rağmen; son bölümdeki çalışmamız daha büyük p ve m değerleri kullanmamıza izin vererek, önerilen polinom seçenekleri ile kullanıldığında Ostafe'ninyönteminin rassal sayı üreteci olarak gerçeklenemeyeceği konusundaki çıkarımımızıdesteklemektedir.

We examine the randomness properties of the sequences generated by the multivariatepolynomial iterations method proposed by Ostafe and Shparlinski, by using the sixdifferent choices of polynomials given by the same authors. Our analysis is based ontwo approaches: distributions of the periods and linear complexities of the producedvector sequences. We define the efficiency parameters, PE for `period efficiency` andLCE for `linear complexity efficiency`, so that the actual values of the period and linearcomplexity 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 generatedvector sequences, we perform an exhaustive search for prime field sizes up to 13; andobserve that the probability of attaining a maximum-period sequence is extremely low.Linear complexities of the sequences are also computed exhaustively for prime fieldsizes up to 13 and the multivariate polynomial iterations with the proposed polynomialchoices are observed to generate sequences with having high linear complexitiesquite seldomly. We then concentrate on the largest period sequences produced by eachchoice, and investigate the linear complexity of those sequences for a given polynomialchoice, at a specific field size p and number of polynomials m. We observe thatan increase of p or m does not bring any improvement on the randomness of the generatedsequences. Finally, we analyze the linear complexity of Ostafe's sequences byfixing the period but leaving the choice of m and other initial values random, as in reallife. Although computational constraints limit our exhaustive search results in the firstpart to relatively small values of p and m; the last part of our study lets us use highervalues of p and m, to justify the projection that Ostafe's method with the proposedpolynomial choices is not a promising way of implementing pseudo-random numbergenerators.