최대무게다항식에 대응하는 난수생성기에 대한 연구

Abstract

In order to design the pseudorandom number generator(PRNG) directly on the hardware, it should be possible to make it using the logic circuit. A linear finite state machine(FSM), which can be fabricated based on linear recurrence, facilitates fabrication using logic circuits. A linear FSM typically includes a linear feedback shift register(LFSR) and a linear cellular automata(CA). A linear FSM can represent a state using a state transition matrix, and the characteristics of a linear FSM can also be analyzed by analyzing this state transition matrix. What is used to analyze the state transition matrix is the characteristic polynomial corresponding to the state transition matrix. Since the characteristics of the linear FSM depend on what the characteristic polynomial is, it is important to determine the appropriate characteristic polynomial for the linear FSM suitable for the application. In this thesis, we analyze the characteristics of the PRNG, especially the CA corresponding to the maximum weight polynomial which is a polynomial with all coefficients 1 over GF(2). The results of the algorithm for the synthesis method for 90/150 CA corresponding to the maximum weight polynomial are also introduced.