Patent ID: 7421463

Claim:
A random sequence generating apparatus for generating a sequence of integers of w bits, comprising: a seed receiving section which receives a sequence of integers s 1 , s 2 , . . . , s n , . . . , s m of w bits as a seed for integers n and m (1≦n≦m−1); an initialization section which provides a transformation section with said received sequence of integers s 1 , s 2 , . . . , s n , . . . , sm as an integer sequence x 1 , x 2 , . . . , x n , . . . , x m ; said transformation section which performs predetermined transformation on each of said provided integer sequence x 1 , x 2 , . . . , x n , . . . , x m to acquire a sequence of integers y 1 , y 2 , . . . , y n , . . . , y m of w bits; a rotation section which acquires a number of rotation bits from said sequence of integers y n+1 , . . . , y m , performs a rotation operation on said acquired number of rotation bits with respect to all of or a part of said sequence of integers y 1 , y 2 , . . . , y n , . . . , y m taken as a bit sequence of wm bits, and acquires a sequence of integers z 1 , z 2 , . . . , z n , . . . , z m of w bits from said acquired bit sequence of wm bits; an updating section which provides said transformation section with said sequence of integers z 1 , z 2 , . . . , z n , . . . , z m as said integer sequence x 1 , x 2 , . . . , x n , . . . , x m ; and an output section which outputs a sequence of integers z 1 , z 2 , . . . , z n or z n+1 , . . . , z m obtained last as a random sequence r 1 , r 2 , . . . , r n or r 1 , . . . , r m−n respectively in case where transformation in said transformation section and rotation in said rotation section are repeated a predetermined number of times, a mapping g(•, •) defined as g ( a, b )=2 b 2 +h ( a ) b+q (mod 2 w ) with h(•) being a predetermined mapping and q being a predetermined integer (0≦q≦2 w−1 ), the mapping h(•) being defined by an operation of setting 01 to least significant two bits in a numerical expression of a given value, wherein the transformation section performs the predetermined transformation by the following recursion formulae for an integer i (1≦i≦m−1): y 1 =g ( x m , x 1 ), y i+1 =g ( x i , x i+1 ), wherein the transformation section performs the predetermined transformation by the following recursion formulae for an integer i (1≦i≦m−1) and a predetermined integer c: y 1 =g ( c, x 1 ), y i+1 =g ( y i , x i+1 ), or wherein the transformation section performs the predetermined transformation by the following recursion formulae for an integer i (1≦i≦m−1) and a predetermined integer c: y 1 =g ( c, x 1 ), y i+1 =g ( x i , x i+1 ).