The aim of this paper is to generate and examine a pseudorandom sequence over a finite field using the Möbius function. In the main part of the paper, after generating a number of sequences using the Möbius function, we examine the sequences’ pseudorandomness using autocorrelation and prove that the second half of any sequence in F_3^n is the same as the first, but for the sign of the terms. I reach the conclusion, that it is preferable to generate sequences in fields of the form F_3^n, thereby obtaining a sequence of the numbers -1, 0, 1, each of which appear in the same amounts. There is a variety of applications of the discussed pseudorandom generator and other generators such as cryptography or randomized algorithms.

Randomness in a mathematical point of view is a tricky and challenging term to define, though each of us has a slight intuition of what it should be. In fact, it is still a question of whether there even exists a source of true randomness. Instead, we rather use the term pseudorandomness which captures something difficult to predict, but not impossible. For scientific purposes we are mostly interested in pseudorandom sequences of numbers since these can be used in computer science for randomized algorithms, which are often faster than normal ones, or, most importantly, cryptography. In this article, we focus on generating a pseudorandom sequence by using an algebraic structure, called finite field, and the Möbius function. The approach used for generating pseudorandom sequences was published quite recently, namely in 2016, and is therefore worth examining further. I decided to study the behaviour of the sequences by applying simple statistical tests: the frequency test and autocorrelation, which reflects the independence of the members of the sequence on one another. After obtaining results from the aforementioned tests, I discovered two intriguing properties of the sequence. Namely, if we choose the finite fields of characteristic 3, the halves of the sequences are the same except for a sign, thus showing us a kind of strong dependence not acceptable in, for instance, cryptography. In addition, when fields of different characteristic are used, the produced sequences’ members will not be completely uniformly distributed, which is usually an important requirement for the sequence to resemble random behaviour.

Václav Zvoníček is currently studying the 2nd grade of Computer Science at the Faculty of Mathematics and Physics at Charles University, Prague. Václav is also a former student of Gymnázium Brno, třídy Kapitána Jaroše in Brno, where he was a student of a mathematical class which encouraged him to a special emphasis on mathematics and physics. During the high school studies, Václav was mainly interested in mathematics, physics and computer science. His interest thus results into the participation in several STEM-based competitions, such as Mathematics and Physics Olympiads or Students’ Professional Activities (SPA). He achieved the nomination to European Physics Olympiad in Riga, Learned Society Award (for his first SPA contribution), and 2nd place in the national round of SPA in 2020 (Mathematics and Statistics). Apart from his academic interests, he also likes to play the piano and do as many sport activities as possible. In the future, He would like to take part in a research in Austria, Germany or Switzerland, mainly aiming at data processing problems or quantum computing.

J. ASB Soc., 2021, 2(1), 36-42

DOI: https://doi.org/10.51337/JASB20211227005

BibTeX Download: Zvoníček – BibTEX file