Compression and randomness applications on the mycielski prediction algorithm

In this thesis, compression and pseudorandom number generation for encryptionproperties of the Mycielski algorithm are investigated. Mycielski predictor is a deterministicalgorithm which uses infinite history. Therefore, the time complexity of the algorithmdiverges for long sequences. In the first part of this work, a time reinforcement of Mycielskialgorithm is discussed and the modified algorithm is used as compression algorithm. Due tothe resemblence of the time improvement to the famous LZ78 compression algorithm, theproposed method is named the Mycielski78 algorithm. In the second part of this work,random number generation properties of the Mycielski predictor is investigated. Analgorithm, called the Antimycielski algorithm, which produces sequences that are orthogonalto the Mycielski prediction output starting from an initial key sequence, is developed. Therandomness quality and cryptography strength of the Antimycielski sequences are examined.Again, due to the complexity of the algorithm, the history used for making prediction that getslonger than a constant limit must be chopped. Performance effects of key length and historychopping length on randomness are examined.Keywords: Predictive Coding, Random Number Generator, Mycielski Predictor,Antimycielski, Ciphering, Blok Ciphers.ii