Implementacja multiplikatywnych generatorów kongruencyjnych z modulnikiem w układzie FPGA

• Autorzy: Jaworski M. , Jessa M.

Identyfikatory

DOI

10.15199/ELE-2014-212

Warianty tytułu

EN

An FPGA implementation of multiplicative congruential generators with modulus

• Języki publikacji: PL

Abstrakty

PL

W pracy opisano uniwersalną metodę implementacji rodziny generatorów pseudolosowych bazujących na multiplikatywnym generatorze kongruencyjnym z modulnikiem 231 -1. Algorytm optymalizuje zarówno operację modulo jaki i operację mnożenia. Projekt został przygotowany w języku Verilog i zaimplementowany w układzie programowalnym FPGA (ang. Field Programmable Gate Array) o symbolu XC6SLX45 firmy Xilinx. Pojedynczy generator zajmuje około 130 komórek typu Slice i może wytwarzać ciąg pseudolosowy o szybkości 4.169 Gbits na sekundę. Zaimplementowany generator nie jest generatorem bezpiecznym, ale może zostać wykorzystany w kryptografii po dodatkowym przetworzeniu ciągu wyjściowego.

EN

A universal hardware implementation of a pseudorandom number generators family based on a multiplicative congruential generator (MCG) with modulus 231 -1 has been proposed in this paper. The proposed algorithm optimizes both the multiplication and modulo 231 -1 operation. The design was prepared in Verilog and implemented in Xilinx Field Programmable Gate Array (FPGA) device XC6SLX45. A single generator takes up about 130 slices and can produce up to 4.169 Gbits per second. Implemented generators are not secure themselves, but they can be used in cryptography with additional processing and by using several different generators in parallel.

Słowa kluczowe

PL

generator liczb pseudolosowych; multiplikatywny generator kongruencyjny; układy FPGA

EN

pseudorandom number generators; multiplicative congruential; generators; field programmable gate array; FPGA

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2014
• Tom: Vol. 55, nr 12
• Strony: 14--16
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Jaworski M.

• Politechnika Poznańska, Wydział Elektroniki i Telekomunikacji

autor

Jessa M.

• Politechnika Poznańska, Wydział Elektroniki i Telekomunikacji

Bibliografia

• [1] D. E. Knuth, The Art of Computer Programming, 3rd ed. vol. 2, Reading MA: Addison-Wesley, 1998.
• [2] J. E. Gentle, Random Number Generation and Monte Carlo Methods, New York: Springer, 2003.
• [3] http://en.wikipedia.org/wiki/Mersenne_prime.
• [4] S.Park, K. Miller, “Random numbers generators: good ones are hard to find,” Communications of the ACM, Volume 31, Issue 10, Oct. 1988, pp. 1192-1201.
• [5] Lan Jingjing, Goh Wang Ling, Kong Zhi Hui and Yeo Kiat Seng, “A random number generator for low power cryptographic application,” IEEE Trans. SoC Design, ISOCC 2010, pp. 328-331.
• [6] J. T. Butler, T. Sasao, “Fast Hardware Computation of x Mod z,” IEEE Trans. Parallel and Distributed Processing Workshops and Phd Forum, IPDPSW’2011, pp. 294-297.
• [7] JunKyu Lee, G.D. Peterson, R.J. Harrison, R.J. Hinde, “Hardware accelerated Scalable Parallel Random Number Generators for Monte Carlo methods”, Circuits and Systems, 2008. MWSCAS’2008. pp. 177-180.
• [8] R. Saini, S. Singh, A.K. Saini, A.S. Mandal, C. Shekhar, “Design of a fast and efficient hardware implementation of a random number generator in FPGA,” International Conference on Advanced Electronic Systems, ICAES’ 2013, Sept. 2013, pp.131-132.
• [9] M. Jessa, M. Jaworski, “High-Speed FPGA-Based Pseudorandom Generators with Extremely Long Periods,” in Proc. Int. Conf. on ReConFigurable Computing and FPGAs, ReConFig’10, Dec. 2010, pp. 286-291.
• [10] M. Jessa, M. Jaworski, “A new source of secure pseudorandom numbers exploiting IMCGs implemented in an FPGA,” in Proc. 13th International Symposium on Integrated Circuits, ISIC’2011, Dec. 2011, pp. 585-588.
• [11] David G. Carta, “Two Fast Implementations of the Minimal Standard Random Number Generator,” Communications of the ACM, Volume 33 Issue 1, Jan. 1990, pp. 87-88.