Thesis supervisor: Tamás Herendi
Location of studies (in Hungarian): Debreceni Egyetem Informatikai Kar Abbreviation of location of studies: DE IK
Description of the research topic:
Linear recurring sequences over finite algebraic structures are often used for pseudo random number seqence generator. The main result in [1] states that for every linear recurring sequence there exists an integer s, depending only on the order of the recursion, such that for any prime p the sequence is uniformly distributed modulo pt for all t, if and only if the sequence is uniformly distributed modulo ps. The result can be improved in some particular case, when p=2. Then s=2 can be proved. Based on this refinement, one can give an algorithm, which tests the uniform distribution of the sequence by the observation of some of its values. However, the computation of these values is rather time consuming task. One of the possible solutions uses exponentiation of huge matrices to a large power. This approach applies very simple operations modulo 4 which can be executed simultaneously. A natural idea to use FPGA for the execution of the task. The PhD student choosing the subject has the primary goal of developing fast and efficient parallel algorithms and implementing them on FPGA, in particular on a Ryviear server with 16 FPGA module .
Bibliography
[1] T. Herendi: Uniform distribution of linear recurrences modulo prime powers J. Finite Fields And Applications 10 (2004), 1-23
[2] R. Lidl, H. Niederreiter: Finite Fields, Cambridge University Press, 1997.
[3] O. Strauch, S. Porubský: Distribution of Sequences: A Sampler, Frankfurt am Main, Berlin, Bern, Bruxelles, New York, Oxford, Wien, 2005. XXII, 543 pp. ISBN 978-3-631-54013-8 pb.
[4] M. Drmota, R.F. Tichy: Sequences, Discrepancies and Applications, Springer Berlin Heidelberg, Lecture Notes in Mathematics (1651), 1997
Recommended language skills (in Hungarian): angol Number of students who can be accepted: 1
Deadline for application: 2018-11-15
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Login
