SCIENCE CHINA Information Sciences, Volume 61, Issue 8: 082304(2018) https://doi.org/10.1007/s11432-017-9279-3

## A pseudo-random sequence generation scheme based onRNS and permutation polynomials

• AcceptedOct 10, 2017
• PublishedMay 18, 2018
Share
Rating

### Abstract

Long period pseudo-random sequence plays an important role in modern information processing systems. Base on residue number system (RNS) and permutation polynomials over finite fields, a pseudo-random sequence generation scheme is proposed in this paper. It extends several short period random sequences to a long period pseudo-random sequence by using RNS. The short period random sequences are generated parallel by the iterations of permutation polynomials over finite fields. Due to the small dynamic range of each iterative calculation, the bit width in hardware implementation is reduced. As a result, we can use full look-up table (LUT) architecture to achieve high-speed sequence output. The methods to find proper permutation polynomials to generate long period sequences and the optimization algorithm of Chinese remainder theorem (CRT) mapping are also proposed in this paper. The period of generated pseudo-random sequence can exceed $2^{100}$ easily based on common used field programmable gate array (FPGA) chips. Meanwhile, this scheme has extensive freedom in choosing permutation polynomials. For example, 10905 permutation polynomials meet the long period requirement over the finite field $F_q~$ with$q~\not\equiv~1({\rm~mod}3)$ and $q\leq503$. The hardware implementation architecture is simple and multiplier free. Using Xilinx XC7020 FPGA chip, we implement a sequence generator with the period over $2^{50}$, which only costs 20 18kb-BRAMs (block RAM) and a small amount of logics. And the speed can reach 449.236 Mbps. The National Institute of Standards and Technology (NIST) test results show that the sequence has good random properties.

### Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant No. 61571083).

Appendix

### References

[1] Figueiredo F A P D, Mathilde F S, Cardoso F A C M, et al. Efficient FPGA-based mplementation of a CAZAC sequence generator for 3GPP LTE. In: Proceedings of International Conference on ReConFigurable Computing and FPGAs (ReConFig14), Cancun, 2014. 1--6. Google Scholar

[2] Nawkhare R, Tripathi A, Pokle P. DS-SS communication system using pseudo chaotic sequences generator. In: Proceedings of International Conference on Communication Systems and Network Technologies, Gwalior, 2013. 78--82. Google Scholar

[3] Peinado A, Munilla J, F$\acute{\rm~~u}$ster-Sabater A, et al. Improving the period and linear span of the sequences generated by DLFSRs. In: Proceedings of International Joint Conference SOCO'14-CISIS'14-ICEUTE'14, Bilbao, 2014. 397--406. Google Scholar

[4] Mandal K, Gong G. Feedback reconstruction and implementations of pseudorandom number generators from composited De Bruijn sequences. IEEE Trans Comput, 2016, 65: 2725-2738 CrossRef Google Scholar

[5] Yang B, Liao X. Period analysis of the Logistic map for the finite field. Sci China Inf Sci, 2017, 60: 022302 CrossRef Google Scholar

[6] Zhou Y C, Hua Z Y, Pun C-M. Cascade chaotic system with applications. IEEE Trans Cybern, 2015, 45: 2001-2012 CrossRef PubMed Google Scholar

[7] Taleb F. A new chaos based image encryption scheme using chaotic logistic maps. In: Proceedings of International Conference on Multimedia Computing and Systems (ICMCS), Marrakech, 2014. 1222--1228. Google Scholar

[8] Araki S, Muraoka H, Miyazaki T, et al. A design guide of renewal of a parameter of the logistic map over integers on pseudorandom number generator. In: Proceedings of International Symposium on Information Theory and Its Applications (ISITA), Monterey, 2016. 781--785. Google Scholar

[9] Corinto F, Krulikovskyi O V, Haliuk S D. Memristor-based chaotic circuit for pseudo-random sequence generators. In: Proceedings of the 18th Mediterranean Electrotechnical Conference (MELECON), Lemesos, 2016. 1--3. Google Scholar

[10] Oliver N, Soriano M C, Sukow D W. Fast random bit generation using a chaotic laser: approaching the information theoretic limit. IEEE J Quantum Electron, 2013, 49: 910-918 CrossRef ADS Google Scholar

[11] Chester D B, Michaels A J. Digital generation of a chaotic numerical sequence. US Patent, US2008/0263119. Google Scholar

[12] Michaels A J. A maximal entropy digital chaotic circuit. In: Proceedings of IEEE International Symposium of Circuits and Systems (ISCAS), Rio de Janeiro, 2011. 717--720. Google Scholar

[13] Hu J H, Ma S. High Speed Digital Signal Processing Application Based on Residue Number System. Beijing: Chinese Science Publishing & Media Ltd., 2012. 1--25. Google Scholar

[14] Khachatrian G, Kyureghyan M. A new public key encryption system based on permutation polynomials. In: Proceedings of IEEE International Conference on Cloud Engineering, Boston, 2014. 540--543. Google Scholar

[15] Sun Q, Wan D Q. Permutation Polynomials and Their Applications. Harbin: Harbin Institute of Technology Press, 2012. 22--55. Google Scholar

[16] Lidi R, Niederreiter H, Cohn F M. Finite Fields. London: Cambridge University Press, 1984. 347--389. Google Scholar

[17] Rukhin A, Soto J, Nechvatal J, et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. National Institute of Standards and Technology (NIST), Special Publication 800-22 Revision 1a, 2010. Google Scholar

[18] Xu D, Xue X X, Wang T, et al. Research on chaotic pseudo random bit generator based on logistic map. Microelectron Comput, 2016, 2: 1--6. Google Scholar

• Figure 1

The proposed pseudo-random sequence generation method base on permutation polynomial and RNS.

• Figure 4

The FPGA implementation architecture.

• Figure 5

The FPGA implementation architecture of traditional method.

• Table A1   The standard permutation polynomials of degree at most five over all finite fields
 The standard permutation polynomial over finite field $F_q$ $q$ $x$ Any value $x^2$ $q~\equiv~0(\boldsymbolod~2)$ $x^3$ $q\not~\equiv~1(\boldsymbolod~~3)$ ${x^3}~-~ax$ ($a~\in~{F_{\rm{q}}}$ $a$ a not a square) $q~\equiv~0(\boldsymbolod~~3)$ ${x^4}~\pm~3x$ $q=7$ ${x^4}~+~{a_1}{x^2}~+~{a_2}x$ ( if $x=0$ is the exclusive root in $F_q$) $q~\equiv~0(\boldsymbolod~~2)$ $x^5$ $q\not~\equiv~1(\boldsymbolod~~~5)$ ${x^5}~-~ax$ ($a~\in~{F_{\rm{q}}}$) ( $a$ not a fourth power) $q~\equiv~0(\boldsymbolod~~5)$ ${x^5}~-~ax$ $({a^2}~=~2)$ $q~=9$ ${x^5}~\pm~2x^2$ $q=7$ ${x^5}~+~a{x^3}~\pm~{x^2}~+~3{a^2}x$ ($a~\in~{F_{\rm{q}}}$ $a$ not a square) $q=7$ ${x^5}~+~a{x^3}~+~{5^{~-~1}}{a^2}x$ ($a$ arbitrary) $q~\equiv~\pm~2(\boldsymbolod~~5)$ ${x^5}~+~a{x^3}~+~3{a^2}x$ ($a~\in~{F_{\rm{q}}}$ $a$ not a square) $q=13$ ${x^5}~-~2a{x^3}~+~{a^2}x$ ($a~\in~{F_{\rm{q}}}$ $a$ not a square) $q\equiv~0(\boldsymbolod~~5)$
•

Algorithm 1 An algorithm for selecting the constant term of permutation polynomial with the longest iterative period

Choosing a permutation polynomial ${\left\langle~{f(x)}~\right\rangle~_m}$;

${x_0}~=~k$, ${x_1}~=~{\left\langle~{f({x_0})~+~c}~\right\rangle~_m}$ %setting iterative initial value and computing the corresponding results;

for $c~=~0,\ldots,m~-~1$ %the value range of constant term $c$ in permutation polynomial;

for $i~=~1,\ldots,m$ %the number of iteration is increasing;

${x_{i~+~1}}~=~{\left\langle~{f({x_i})~+~c}~\right\rangle~_m}$; %iterative polynomial computation;

if ${x_{i~+~1}}~=~{x_1}$ %if the current result equal to initial result; then

break;

if $i~\ne~m$ %if the current result equals to initial result and the number of iteration does not equal to $m$; then

loop period is $i$; %multiple-loop situation are existing, constant $c$ does not satisfy the longest period property;

else

loop period is $m$; %iterative period reached maximum, constant $c$ satisfy the longest period property;

end if

end if

end for

end for

• Table 1   Test results for the proposed pseudo-random sequence generation scheme
 Test item Passing rate $~p\_{\rm~value}$ $p\_{\rm~value}$ Passing rate [6] $p\_{\rm~value}$ [6] ${{p}}\_{\rm~value}~>~0.01$ Average Std ${{p}}\_{\rm~value}~>~0.01$ Average Frequency test 99.20% 0.4994 0.1372 98.00% 0.1538 Frequency test within a block 99.15% 0.4948 0.0182 99.00% 0.7792 Runs test 98.65% 0.5065 0.3433 100.00% 0.4944 Test for the longest run 99.05% 0.4971 0.1705 99.00% 0.5141 Binary matrix rank test 98.70% 0.4985 0.0935 99.00% 0.8832 Discrete Fourier transform 99.00% 0.4842 0.2865 98.00% 0.0428 Non-overlapping template 99.20% 0.5043 0.0986 98.38% 0.4794 Overlapping template 98.90% 0.5249 0.1426 100.00% 0.2493 Maurer's universal 98.75% 0.4960 0.6358 100.00% 0.1917 Linear complexity test 99.00% 0.5034 0.0218 98.00% 0.1154 Serial test 98.85% 0.4936 0.4220 98.50% 0.2523 Approximate entropy test 98.85% 0.5012 0.4215 99.00% 0.4373 Cumulative sums test 99.35% 0.5012 0.1212 98.00% 0.5087 Random excursions test 97.75% 0.5183 0.3868 98.89% 0.4506 Random excursions variant 98.95% 0.5134 0.3046 99.01% 0.2544 The number of success items 15/15 – – 15/15 –
• Table A2   A few permutation polynomials over finite field $F_q$ and $q~\not\equiv~1(\boldsymbolod~3)$ and $q~\le~503$ with single iterative loop
 $m$ $\{~q,r,s,c\}~$ 11 $\{~1,1,4,1\},\{~1,6,1,2\},\{~1,4,9,3\},\{~1,3,3,4\},\{~1,2,5,5\},\{~1,10,4,10\}~$ 47 $\{~1,22,36,1\},\{~1,31,7,2\},\{~1,7,32,3\},\{~1,24,5,4\},\{~1,25,36,46\}~$ 59 $\{~1,24,15,2\},\{~1,40,22,3\},\{~1,18,49,4\},\{~1,25,51,5\},\{~1,5,28,57\}~$ 71 $\{~1,39,10,1\},\{~1,67,29,2\},\{~1,12,48,3\},\{~1,19,2,4\},\{~1,32,10,70\}~$ 83 $\{~1,21,64,1\},\{~1,51,37,2\},\{~1,6,12,3\},\{~1,32,37,4\},\{~1,62,64,82\}~$ 131 $\{~1,27,112,1\},\{~1,62,15,2\},\{~1,63,13,3\},\{~1,11,84,5\},\{~1,16,129,130\}~$ 251 $\{~1,12,48,1\},\{~1,103,106,2\},\{~1,15,75,3\},\{~1,57,79,4\},\{~1,239,48,250\}~$ 311 $\{~1,84,175,1\},\{~1,23,280,2\},\{~1,36,121,3\},\{~1,40,15,4\},\{~1,227,175,310\}~$ 347 $\{~1,244,182,1\},\{~1,33,16,3\},\{~1,115,13,6\},\{~1,38,250,8\},\{~1,103,182,346\}~$ 443 $\{~1,163,144,1\},\{~1,240,151,2\},\{~1,25,356,3\},\{~1,57,197,5\},\{~1,280,144,442\}~$ 467 $\{~1,396,435,1\},\{~1,288,95,2\},\{~1,82,62,3\},\{~1,31,9,5\},\{~1,71,435,466\}~$ 479 $\{~1,69,150,1\},\{~1,324,25,2\},\{~1,67,219,3\},\{~1,53,138,5\},\{~1,410,150,478\}~$ 491 $\{~1,21,147,1\},\{~1,127,139,2\},\{~1,33,363,3\},\{~1,10,197,5\},\{~1,470,147,490\}~$ 503 $\{~1,109,104,1\},\{~1,267,122,2\},\{~1,271,1,3\},\{~1,8,189,5\},\{~1,394,104,502\}~$
• Table 2   The number of items which failed in individual sequence set testing
 The number of items $p\_{\rm~value}<~0.001$ in each 15 test items The number of sequence sets 5 2 4 3 3 7 2 37 1 215 0 1736 Total 2000
• Table 3   Implementation comparison based on FPGA
 Traditional architecture Proposed architecture LUT 681 (1%) 245 (0%) Register 181 (0%) 52 (0%) BRAM 0 (0%) 20 (14%) DSP 27 (12%) 0 (0%) Generated speed 39.853 Mbps 449.236 Mbps Period $2^{40}$ $2^{90}$
• #### 1

Citations

• Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有