(****************************************************************) (* General Shift Registers V 1.0 *) (* Klaus Pommerening *) (* 17. Juli 2008 *) (* Last Change: 20. Juli 2008 *) (****************************************************************) (****************************************************************) (* This Mathematica program module deals with Boolean *) (* functions of n (binary) variables, represented in algebraic *) (* normal form (ANF). *) (* It uses them for constructing general shift registers that *) (* have an - in general nonlinear - Boolean feedback function. *) (****************************************************************) (****************************************************************) (* This program module uses the following data structures: *) (* Bit list or binary vector: A list of integers 0 or 1 *) (* - A bit list may be represented by the integer whose *) (* base 2 representation is given by this bit list, *) (* less significant bits at the right end. *) (* Binary monomial in several variables *) (* - A monomial is represented by a bit list or by the *) (* corresponding integer. Explanation: *) (* n Bits {e1, ...,en} define a binary monomial in n *) (* Variables T1, ..., Tn as follows: *) (* T1^e1 ... Tn^en. *) (* Boolean function in Algebraic normal form (ANF) *) (* - A Boolean function of n variables in ANF is specified *) (* by the list of monomials in n indeterminates T1, ..., Tn *) (* that have coefficient 1. Each monomial in turn is *) (* specified by a bit list or an integer. *) (* Note: This representation of Boolean functions makes *) (* sense only for small n or for sparse polynomials. *) (* Integer *) (* - An integer may represent itself, a bit list or a binary *) (* monomial. *) (* NOTE: LSBs = least significant bits, *) (* MSBs = most significant bits. *) (****************************************************************) (****************************************************************) (* i2b: Convert integer to bit list. *) (* Gives the list of n LSBs of the integer x. *) (* Input parameters: n = length of the wanted list *) (* x = number to be decomposed into bits *) (* Preconditions: n >= 1, 0 <= x <= 2^n -1 *) (* Error and special situations: *) (* If n <= 0, the output is the empty list {}. *) (* If x <= 0, set x = 0. *) (* If x >= 2^n, truncate excess MSBs. *) (* If x < 2^(n-1), pad left end of list with zeroes. *) (****************************************************************) i2b[n_Integer,x_Integer]:= Module[{y,binDig,l}, If[n<=0,Return[{}],]; If[x<0,y=0,y=x]; binDig=IntegerDigits[y,2]; l=Length[binDig]; If[l>n, Return[Drop[binDig,l-n]], Return[Join[Table[0,{n-l}],binDig]]] ] (****************************************************************) (* b2i: Convert bit list to integer. *) (* b2i interprets a binary vector as integer in base 2 *) (* representation and returns this integer. *) (* Input parameter: binlist = list of bits *) (* MSB to the left, LSB to the right *) (* Preconditions: binlist consists of 0's and 1's. *) (* Error situation: If binlist contains other entries, the *) (* result is anything. *) (****************************************************************) b2i[binlist_]:= Module[{l,i,a=0}, l=Length[binlist]; Do[a=a+binlist[[i]]*2^(l-i),{i,l}]; Return[a] ] (****************************************************************) (* monAtB: Evaluate monomial at binary vector. *) (* monAtB evaluates the monomial given by the list of n LSBs *) (* of the integer e at the n-tuple bitl. *) (* Input parameters: n = number of variables/ arguments *) (* e = integer describing the monomial *) (* i. e. the exponent vector *) (* bitl = argument vector *) (* Preconditions: n >= 1, 0 <= e <= 2^n -1 *) (* bitl has length n and consists of 01 and 1s. *) (* Error and special situations: *) (* If n <= 0, the return value is 0. *) (* If e is outside its range, this is handled by i2b. *) (* If bitl is shorter then n, the function fails. *) (* If bitl is longer than n, the exceeding bits to the right *) (* are ignored. *) (* Note: If e gives the zero exponent vector (that is e<=0), *) (* the monomial is the constant 1 and therefore gives the *) (* value 1 at any argument vector (except when n<=0). *) (* Calls: i2b *) (****************************************************************) monAtB[n_Integer,e_Integer,bitl_]:= Module[{exponents,value=1,i}, If[n<=0,Return[0],]; exponents=i2b[n,e]; For[i=1,i<=n,i++, If[exponents[[i]]==1,value=value*bitl[[i]],] ]; Return[value] ] (****************************************************************) (* monAtI: Evaluate monomial at binary vector represented *) (* by an integer. *) (* monAtI evaluates the monomial given by the list of n LSBs *) (* of the integer e at the n-tuple of n LSBs of the integer x.*) (* Input parameters: n = number of variables/ arguments *) (* e = integer describing the monomial *) (* i. e. the exponent vector *) (* x = integer describing the argument vector *) (* Preconditions: n >= 1, 0 <= e, x <= 2^n -1 *) (* Error and special situations: *) (* If n <= 0, the return value is 0. *) (* If e or x are outside their ranges, this is handled *) (* by i2b. *) (* Note: If e gives the zero exponent vector (that is e<=0), *) (* the monomial is the constant 1 and therefore gives the *) (* value 1 at any argument vector (except when n<=0). *) (* Calls: i2b, monAtB *) (****************************************************************) monAtI[n_Integer,e_Integer,x_Integer]:= Module[{arguments,value}, If[n<=0,Return[0],]; arguments=i2b[n,x]; value=monAtB[n,e,arguments]; Return[value] ] (****************************************************************) (* cleanANF: Take a list of integers and force each entry into *) (* the range [0 ... 2^n-1]. Then remove repeating entries. *) (* Input parameters: n = the number of variables *) (* intlist = the list of integers *) (* representing the monomials occuring in *) (* an ANF. *) (* Preconditions: n>=1 *) (* intlist consists of integers. *) (* Error situations: If n<=0, then output is the empty list. *) (* The case of non-integer entries in *) (* intlist is not caught and gives *) (* unpredictable results. *) (****************************************************************) cleanANF[n_Integer,intlist_]:= Module[{l,i,dummylist,cleanlist}, If[n<=0,Return[{}],]; dummylist=intlist; l=Length[dummylist]; For[i=1,i<=l,i++, If[dummylist[[i]]<0,dummylist=ReplacePart[dummylist,0,i],]; If[dummylist[[i]]>=2^n,dummylist=ReplacePart[dummylist,Mod[dummylist[[i]],2^n],i],] ]; cleanlist=Union[dummylist]; Return[cleanlist] ] (****************************************************************) (* evalBFatB: Evaluate a Boolean function of n variables, *) (* given in ANF, at a binary argument vector. *) (* Input parameters: n = number of variables/ arguments *) (* monList = list of monomials *) (* bitl = argument vector *) (* Preconditions: n>=1 *) (* monList consists of integers *) (* bitl consists of 0s and 1s. *) (* Error situations: If n<=0, then the return value is 0. *) (* The case of non-integer entries in *) (* monList is not caught and gives *) (* unpredictable results. *) (* Non admissible values in bitl are handled *) (* by monAtB. *) (* Calls: cleanANF, monAtB *) (* Indirect call: i2b *) (****************************************************************) evalBFatB[n_Integer,monList_,bitl_]:= Module[{value=0,newlist,l}, If[n<=0,Return[0],]; newlist=cleanANF[n,monList]; l=Length[newlist]; Do[value=value+monAtB[n,newlist[[i]],bitl],{i,l}]; Return[Mod[value,2]] ] (****************************************************************) (* evalBFatI: Evaluate a Boolean function of n variables at an *) (* n dimensional binary argument vector, given by the *) (* base 2 representation of an integer. *) (* Input parameters: n = number of variables/ arguments *) (* monList = list of monomials *) (* x = integer describing the argument vector *) (* Preconditions: n>=1 *) (* monList consists of integers *) (* Error situations: If n<=0, then the return value is 0. *) (* The case of non-integer entries in *) (* monList is not caught and gives *) (* unpredictable results. *) (* Non admissible values of x are handled by *) (* monAtI. *) (* Calls: cleanANF, monAtI *) (* Indirect call: i2b, monAtB *) (****************************************************************) evalBFatI[n_Integer,monList_,x_Integer]:= Module[{value=0,newlist,l}, If[n<=0,Return[0],]; newlist=cleanANF[n,monList]; l=Length[newlist]; Do[value=value+monAtI[n,newlist[[i]],x],{i,l}]; Return[Mod[value,2]] ] (****************************************************************) (* shiftReg: Define a general shift register and generate a *) (* bit sequence. *) (* Input parameters: n = length of the register *) (* mlist = list of monomials for the Booelan *) (* feedback function in ANF *) (* seed = bit list describing start vector *) (* q = number of output bits *) (* Preconditions: n>=1 *) (* mlist consists of integers. *) (* seed is a list of length n consisting of 0s *) (* and 1s. *) (* q is an integer >=1. *) (* Error situations: If n<=0, then the output is the empty list *) (* {}. *) (* Entries of mlist outside of 0 ... 2^n-1 *) (* and multiple entries in mlist *) (* are handled by cleanANF. *) (* The case of non-integer entries in *) (* mlist is not caught and gives *) (* unpredictable results. *) (* If the length of seed is < n or > n, the *) (* output is the empty list {}. *) (* Entries other than 0 or 1 in mlist give *) (* undefined results. *) (* If q<=0, then the output is the empty list *) (* {}. *) (* Calls: evalBFatB *) (* Indirect call: cleanANF, i2b, monAtB *) (****************************************************************) shiftReg[n_Integer,mlist_,seed_,q_Integer] := Module[{x,i,y, outlist = {}}, If[n<=0,Return[{}],]; If[Length[seed]n, Return[{}],]; x=seed; For[i=0,i 11. *) (* Generate 40 bits. *) (****************************************************************) shiftReg[4,{3,12},{1,0,1,1},100] {1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1, 0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1, 1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0, 1,1} (****************************************************************) (* Length 3, ANF T1 + T3 = {4,1}, seed 111 -> 7. *) (* Generate 10 bits. *) (* Golomb, p. 29 *) (****************************************************************) shiftReg[3,{1,4},{1,1,1},10] {1,1,1,0,1,0,0,1,1,1} (****************************************************************) (* Length 4, ANF T3 + T4 = {2,1}, seed 1111 -> 15. *) (* Generate 19 bits. *) (* Golomb, p. 111 *) (****************************************************************) shiftReg[4,{1,2},{1,1,1,1},19] {1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1} (****************************************************************) (* Length 3, ANF T2*T3 = {3}, seed 110 -> 6. *) (* Generate 8 bits. *) (* Golomb, p. 115 *) (****************************************************************) shiftReg[3,{3},{1,1,0},8] {0,1,1,0,1,0,0,0} (****************************************************************) (* Length 3, ANF T2*T3 = {3}, seed 100 -> 4. *) (* Generate 8 bits. *) (* Golomb, p. 115 *) (****************************************************************) shiftReg[3,{3},{1,0,0},8] {0,0,1,0,0,0,0,0} (****************************************************************) (* Length 3, ANF T2*T3 = {3}, seed 111 -> 7. *) (* Generate 8 bits. *) (* Golomb, p. 115 *) (****************************************************************) shiftReg[3,{3},{1,1,1},8] {1,1,1,1,1,1,1,1} (****************************************************************) (* Length 4, ANF T1*T2 + T4 = {12,1}, seed 0011 -> 3. *) (* Generate 19 bits. *) (* Golomb, p. 170 *) (****************************************************************) shiftReg[4,{1,12},{0,0,1,1},19] {1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1} (****************************************************************) (* Jetzt Länge steigern *) (****************************************************************) shiftReg[4,{1,12},{0,0,1,1},40] {1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,1, 1,1,1,0,1,1,0,0} shiftReg[4,{1,12},{0,0,1,1},100] {1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,1, 1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1, 0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1,0,1,1,0,0,1,1,1,1, 0,1} (****************************************************************) (* Length 4, ANF T1*T2*T4 + T3 = {13,2}, seed 0011 -> 3. *) (* Generate 100 bits. *) (****************************************************************) shiftReg[4,{2,13},{0,0,1,1},100] {1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0, 0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0, 0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0} shiftReg[8,{1,12,129},{1,0,1,1,0,0,1,1},50] {1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0, 1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1} shiftReg[16,{1,12,129,65000},{1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1},100] {1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0, 1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1, 0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0} shiftReg[32,{1,12,129,65000,123456}, {1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1},200] {1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,0, 1,1,0,1,0,0,0,0,0,0,0,1,1,1,1,0,1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,1, 0,1,0,0,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0,1,1,0,0, 0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0, 0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1, 0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0} shiftReg[32,{1,12,63,129,256,65000,123456,2147483640}, {1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,0},2000] {0,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,0, 0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,1, 0,0,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,1,0,0,1,1,1,0,0,1,0, 0,0,1,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,1,0,0,1,0,1,1,1,0,0,1,0,1,1,0, 0,1,1,0,1,1,0,0,0,1,1,0,0,0,1,1,1,0,0,1,1,0,1,0,1,1,1,1,1,1,0,1,0, 0,0,0,1,1,1,0,1,0,1,1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,0,1,1,0,1,0, 0,0,0,1,1,0,0,0,0,1,1,1,1,0,1,1,0,1,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0, 0,1,1,1,0,1,0,1,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0, 0,0,1,0,0,0,1,1,0,1,1,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,0, 1,1,0,1,0,1,1,1,0,1,0,0,1,0,0,1,1,0,0,1,1,1,1,0,0,1,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,1,0,0,1,1,0,1,0,1,0,1,0,1,1,1,1,0,1,0,0,0,0,0,1,1,0, 0,1,1,0,1,0,0,1,1,0,0,1,1,1,0,1,1,1,0,1,1,0,1,0,0,1,1,1,1,0,1,0,1, 0,1,1,1,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,1,0,0,1,0,1,0,1,1,0,1,0,1,1, 0,0,1,1,0,0,0,1,0,1,1,0,1,0,1,1,0,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,1, 1,1,0,1,0,1,0,0,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,1,0,1,0,0,0,1,1,1,0, 0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,0,0,1,0,0, 1,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,1,0,1,0,0,1,1,0, 1,0,1,0,0,0,1,0,1,0,0,1,0,0,0,1,1,0,1,0,0,0,1,0,0,0,0,1,0,1,0,0,0, 0,1,1,0,0,1,1,1,0,1,0,0,1,1,0,1,0,1,1,0,1,0,0,0,0,1,1,0,1,1,1,0,0, 0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,0,1,0,0,0,0,0,0,0,0, 0,1,0,1,0,0,0,0,1,0,0,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,0,0,0,1, 0,0,0,1,1,0,1,0,0,0,1,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,0,1,0,0, 1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,0,1,1,1,0,0,0,0,1,0,1,1,1,0,0,0,1,0, 1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,1,1,1,0,0,0, 1,1,1,1,0,0,0,1,0,1,0,1,0,1,0,0,1,1,1,0,1,0,1,0,0,0,1,1,0,0,1,0,1, 0,0,0,0,1,0,1,1,1,1,0,1,0,0,1,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,1,1,1, 1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,0,0,0,0,0,1,0,0,0,0,1,0, 0,0,1,0,1,1,1,1,0,1,0,0,0,0,1,1,1,1,0,0,0,0,1,0,0,1,1,0,1,1,1,1,0, 1,1,1,0,1,0,1,1,1,0,0,1,1,1,0,1,0,1,0,1,1,1,0,0,0,0,0,1,0,0,1,0,1, 0,1,1,0,0,0,0,0,0,1,0,1,1,0,1,0,0,1,0,0,1,1,0,1,0,1,1,0,0,1,0,0,0, 0,0,1,1,0,1,0,0,1,0,1,0,1,0,1,0,0,0,0,1,0,0,0,0,1,1,1,1,0,1,0,0,0, 0,0,0,1,0,1,0,1,0,1,1,0,0,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,0,1,0, 1,1,0,0,0,0,1,1,1,1,1,1,0,0,1,0,1,0,0,0,0,1,0,1,0,1,0,0,1,0,1,1,1, 1,1,1,1,1,0,1,1,0,1,1,0,1,0,1,0,1,0,1,1,0,1,1,1,1,1,1,0,0,0,0,1,1, 1,1,0,1,0,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0, 0,1,1,1,1,1,1,1,1,0,0,1,0,0,0,0,0,0,0,0,1,1,1,0,1,0,0,0,1,1,1,0,0, 0,1,0,1,0,1,1,1,0,0,1,1,1,1,0,1,0,1,1,0,1,1,0,1,0,0,1,0,0,1,1,1,0, 1,1,0,0,1,0,0,1,0,0,0,0,1,0,1,0,1,1,0,1,0,1,1,0,1,1,1,1,0,0,0,1,0, 1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1, 0,1,0,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,1,1,0,0,1,0,0,0,1,0,0,0,0,1, 1,0,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,1,1,1,0,0,1,1,0,0,1,1, 1,0,0,0,1,1,0,1,0,0,1,0,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,0,0,0, 0,0,0,1,1,1,1,0,0,0,0,0,1,0,0,0,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,0,0, 1,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,0,1,1,0,1,1,1,1,0,0,1,1,1,0,1,0,0, 1,0,0,0,1,1,0,1,0,1,0,1,1,1,0,0,1,1,0,0,0,0,0,1,0,0,1,1,1,1,0,1,0, 1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,0,0,1,0,0,1,1,1,1,0,0,1, 1,1,1,0,1,1,1,0,1,0,1,0,0,0,0,0,1,0,1,1,1,0,1,0,0,0,1,0,0,0,0,1,0, 0,1,1,1,1,1,0,0,0,0,1,1,0,1,0,0,1,0,0,1,0,1,1,0,0,0,1,1,1,1,0,1,1, 0,1,1,0,0,0,0,0,0,1,0,0,1,1,0,1,0,1,0,1,1,0,1,0,1,1,1,0,0,0,1,0,0, 0,0,0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,1,0,1,0,0, 0,1,1,0,1,0,0,1,0,0,0,0,0,1,1,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,0,0,0, 1,1,0,1,1,1,1,1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,1,1,0,1,0, 1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,0, 1,1,0,1,1,0,0,1,0,0,1,1,1,1,0,1,0,1,0,1,1,0,0,0,0,1,0,1,1,0,0,1,0, 0,1,1,1,1,0,0,1,0,1,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,1,1,1,0,1,0,1, 1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,1,1,0,0,1,0,0,0,1,1,0,1,0,0,0, 0,0,0,0,1,0,0,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,1,0,0,0,0,1,1, 1,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,1,1,0,0,0,1,1,0,1, 1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1,1,0,1,1,0,0,0,0,1,0,1,1,1,0,0,1,1, 1,1,1,0,0,1,1,1,0,0,0,1,0,1,1,1,0,1,1,1,0,0,1,0,0,1,1,0,1,0,0,0,0, 1,1,0,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,0,1} shiftReg[64,{1,12,63,129,256,65000,123456,2147483640}, {1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,0, 1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,1,1,0,1,0,1,1,0,0,1,0},2000] {0,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,0, 1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1,0,1,0,1,1,0,1,0,0,1,0,0, 0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0, 0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,1,0,0, 0,1,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,1,0,0,0, 1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,0,1,1,0,0,1,1,1,0,0,1,0,0,0,1, 0,1,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,1,0,1,0,0,0,1,0, 1,0,0,1,0,0,0,1,0,1,1,0,0,0,1,0,0,1,0,1,1,1,0,0,1,0,0,0,0,1,1,0,1, 0,1,1,0,1,1,0,0,1,1,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1, 1,0,0,0,1,1,0,0,0,1,1,1,0,0,1,1,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0,1,1, 1,0,1,0,1,1,0,1,0,1,1,0,0,1,0,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,1,1,1, 0,1,0,1,1,0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,0,1,1,1,0,1,0,0,0,0,0,0,1, 0,0,1,0,0,1,1,0,0,1,1,1,1,1,1,0,0,0,0,1,0,1,1,0,1,0,0,0,0,1,0,1,1, 0,0,0,1,0,1,0,0,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,0,0,1,0,1,1,1,0,0,1, 1,0,1,1,1,1,1,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,0,1,1,1,0,1,0,1, 0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,0, 0,0,1,0,0,0,0,1,0,0,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,0,1,0,1,1,0,1,0, 0,0,1,1,1,1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,1,0,1,1,1,1,1,1,1,0,0, 0,1,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,1,0,1,1,1, 0,1,1,0,1,0,0,0,0,1,1,1,1,0,1,1,0,0,1,1,0,1,1,1,1,0,0,1,0,0,0,0,1, 0,0,0,0,1,0,0,0,0,1,1,0,1,0,0,1,1,1,1,0,1,0,0,1,0,1,1,0,0,1,0,0,0, 1,1,1,0,1,0,1,0,0,1,1,1,1,1,0,0,1,1,1,0,1,1,0,0,0,1,0,1,0,0,1,0,1, 1,0,0,0,0,0,1,1,1,0,0,1,1,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0, 1,1,1,1,0,1,0,0,0,0,0,1,1,1,1,0,1,1,0,1,1,0,1,1,0,1,0,0,0,1,1,1,0, 0,1,0,0,0,1,0,1,0,1,0,1,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,0,0,1,1,0,1, 1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,0,0,1,0,0, 0,1,0,1,1,1,0,0,0,1,1,1,0,1,1,1,0,0,0,0,0,0,0,1,0,0,1,1,1,1,0,1,0, 1,0,0,1,1,0,0,0,1,0,1,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,1,1,1,0,0,0,1, 0,1,0,0,1,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,1,1,0,1,0,1,0,0,1, 1,1,0,0,1,0,0,1,0,1,0,1,0,1,0,1,1,1,1,0,0,1,0,1,0,0,1,1,0,1,1,1,0, 1,1,0,1,1,1,1,0,1,1,0,0,0,1,1,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0,0,0, 0,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,0,0,1,1,1,1,1,1,0,1,1,0,0,0,0, 1,0,1,0,0,1,0,1,0,0,0,0,1,0,1,1,0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,1,0, 0,0,0,0,0,0,0,0,1,1,0,1,1,1,1,1,1,0,1,1,0,1,1,1,0,0,0,0,1,0,1,0,0, 1,0,1,0,1,1,0,1,0,0,0,1,1,0,0,1,0,1,0,0,1,1,0,0,0,1,1,1,1,1,0,1,1, 0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,0,1,0,1,0,1,1,0,1,0,0, 0,1,1,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,1,0, 1,0,0,1,1,1,0,0,0,0,1,1,1,1,0,1,0,1,1,0,1,0,0,0,1,1,0,0,1,0,1,0,0, 0,1,0,1,0,0,0,0,1,1,0,1,0,0,0,1,1,0,0,0,1,1,0,0,0,0,1,1,1,0,0,1,1, 0,1,1,1,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,1,1, 0,0,0,0,1,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,0,1,1,1,1,1,1,1,1, 1,0,0,1,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,1,1,0,1,0,0,0,1,0,1,1,0,0,1, 0,1,1,0,1,1,0,0,1,1,1,0,0,0,0,1,1,1,1,1,1,0,0,1,0,1,0,1,1,0,1,1,0, 1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,1,1,0,0,1,0,0,1,0,1,1,0,0,1,0,0,1,1, 0,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,0,0,1,0,1,1,0,1,0,1,0,1,0,1,0,0,0, 1,0,1,0,0,1,1,0,1,1,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,1,1,0,0,0,1,0,0, 1,1,0,1,0,1,1,0,0,0,1,1,0,0,0,1,1,1,0,0,0,1,0,0,0,0,0,1,1,1,0,0,1, 0,0,1,0,0,1,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,0,0,0,0,1,1, 1,0,0,1,1,1,0,1,0,1,0,0,1,1,1,1,0,1,1,1,0,0,1,1,1,0,0,1,1,0,1,1,1, 0,1,1,0,0,1,0,0,0,0,1,0,0,0,0,1,0,1,1,1,1,1,1,1,0,0,1,0,0,0,0,0,0, 1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1,1,0,0,0,0,1, 0,0,0,1,0,1,0,1,1,1,1,1,1,0,1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,1,0,1,0, 0,1,0,1,0,0,0,0,0,0,0,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,0,1,1, 1,1,1,1,0,1,1,1,0,0,0,1,0,0,1,1,0,1,1,0,0,0,1,1,1,0,0,0,0,1,0,0,1, 0,0,1,1,1,1,1,1,0,1,0,1,0,0,1,0,1,1,0,0,0,0,1,1,1,1,1,1,0,1,0,1,1, 1,1,1,1,0,1,0,1,1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,1,0, 0,1,1,1,0,0,1,1,0,1,0,0,1,1,1,1,0,1,0,0,0,1,0,1,1,1,1,1,0,0,1,0,0, 0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,1,1,1,1,1,1,0,1,1,0,0,0,0,1,0,0,1,0, 0,1,0,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,1,0,1,1,1,0,1,0,0,0,0,0, 0,0,0,0,1,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,1,0,0,0,1,0,0,1,1,0,0,1,0, 1,1,1,1,0,1,1,1,0,0,1,0,1,0,1,1,0,1,0,0}