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

More info
  • ReceivedJun 15, 2017
  • AcceptedOct 10, 2017
  • PublishedMay 18, 2018


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.


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




[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


    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;


    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}$

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