A5/1 Soft Version Explained VI

Sample of Special States - Inverse Proliferation metric

Some hints about Markovian critical processes

By Juan Chamero, juan.chamero@intag.org, as of April 2006



As we have seen we may generate a “Special States” subset out of a GF2 set of (2^n -1) members characterized by a given “pattern” within their “neighborhood” when generated by a “States Machine”. Remember that we may imagine the whole states sequence along a 2^64 – 1 bits outcome vector. At any position h we may get state S(h) by taking the bit (h) followed by the next (n-1) bits. Along this long vector we may look for some “strange” patterns, like for instance a 1 followed by 15 zeroes. If these patterns have k bits we are going to find approximately 2^(n-k) of such patterns.


If we are talking of a States Machine that runs m time steps to generate m bits outcomes we may define the pattern “neighborhood” set as the set of those states capable to generate these patterns within the m size interval. We may also use the sequence/outcome generation vector to define these neighborhoods.


Have all states within these subsets similar properties?. Well it depends of how they were generated. If generation was based on LFSR’s working linear, as if all registers worked synchronized all at a time, any state have a unique ancestry easy to find going backwards along its outcome vector. However if register activation is ruled by a non linear process any state may be the result of more than one partial states combination, and this characteristic may open more and more possible ancestors as we go upwards. If we have outcome vectors U1, U2 and U3, for each register, of dimensions 2^19-1, 2^22-1, and 2^23-1 respectively, any state at time step (t) could be defined by the following relation:


S(t) = S1(i+t)OS2(j+t)OS3(k+t)


Where S1(i), S2(j), S3(k) are the initial partial states at time t=0, located at positions [i j k] within their respective outcome vectors U1, U2, and U3 that is we obtain S by concatenating (O) three partial states. As time advances working within linearity, the above relation holds true for any t. On the contrary, working within non linearity t advance does not mean registers advance or virtually pointers advance along either component of the triplet [I j k]. For this reason for any state S(t) we may find instead


S(t) = S1(i+t1)OS2(j+t2)OS3(k+t3)


Where at time (t) the triplet [t1 t2 t3] corresponding to triplet [i j k] at time “distance” t is of probabilistic nature with a mean of ¾ of t. Ignoring t, going backwards from any state defined by its 64 bits content (19 in R1, 22 in R2 and 23 in R3), and also ignoring the initial positioning triplet [i j k], has the form of a Markovian process. Each state content may have from none to four possible ancestors with an average of 1 so it’s perfectly possible to find sequences of let’s say 1,2 ancestors along 100 levels which becomes 13,780 possible ancestors!.


We may then define a sort of Reverse Proliferation factor just counting the potential ancestors within certain “bandwidths” measured in levels of backwards trees. This metric is then useful to differentiate Special States in at least two families: Prolific and Non Prolific. Prolific states are those that could be find going forward as “descendants” within the neighborhood of “hidden” states as explained above.


Below we listed a sample of 1000 states whose contents are expressed in hexadecimal. Under X it’s listed the amount of possible ancestors within time steps 100 and 277.



Nr.  EE [R1     R2      R3]     X       Level attained

EE2     [edfb 7b3c3 2684df]    2302    277

EE18    [edfb 1971bf 2c47a0]   3015    277

EE22    [edfb 1e437f 28e740]   3835    277

EE50    [edfb 17f7a0 9037f]    4960    277

EE67    [1dbf7 1f1787 1b83fe]  7024    277

EE71    [1dbf7 167cdf 1c03c3]  1434    277

EE106   [1dbf7 1f7fa0 2037f]   2140    277

EE111   [1dbf7 1f0740 de3fe]   4550    277

EE130   [3b7ef 19f337 1887d0]  3164    277

EE131   [3b7ef df4df 1807d0]   4081    277

EE132   [3b7ef df4df 1807a0]   1933    277

EE154   [3b7ef c9fd0 2710e6]   1570    277

EE157   [3b7ef cbfd0 2421bf]   869     277

EE187   [76fdf 17d1bf 1207d0]  5400    277

EE191   [76fdf d7bfe 8429e]    730     277

EE196   [76fdf affe8 20437f]   893     277

EE233   [5bf7c df1e1 837f]     1232    277

EE237   [5bf7c 2f0e6 3707f4]   1809    277

EE240   [5bf7c 7e1cc 30770e]   1804    277

EE242   [5bf7c 1fee66 801cc]   1174    277

EE264   [5bf7c 1bfff4 10278]   3981    277

EE265   [5bf7c 1bfff4 200e6]   1111    277

EE316   [37ef9 17ffa0 101bf]   1221    277

EE337   [6fdf3 1cf1bf e17d0]   2891    277

EE353   [6fdf3 ef5ff c17a0]    4289    277

EE361   [6fdf3 1ef3fe 82740]   2092    277

EE363   [6fdf3 7fff4 1037f]    4110    277

EE366   [6fdf3 7ffe8 401cc]    1241    277

EE379   [6fdf3 7f7d0 403fe]    4328    277

EE381   [6fdf3 7e7a0 5e1bf]    7511    277

EE382   [6fdf3 7ffa0 2037f]    2122    277

EE394   [5fbe7 1fff87 411e1]   578     277

EE418   [5fbe7 1ef37f 381740]  900     277

EE448   [5fbe7 1f67d0 204df]   2553    277

EE460   [5fbe7 1fe7a0 403fe]   1604    277

EE468   [5fbe7 1fc680 1037f]   759     277

EE471   [3f7cf 1be3c3 18070e]  2576    277

EE472   [3f7cf 1fe3c3 101bf]   2627    277

EE476   [3f7cf f9787 403fe]    2232    277

EE502   [3f7cf ef3fe 1837d0]   3512    277

EE508   [3f7cf fe7e8 1037f]    6199    277

EE516   [3f7cf fe7a0 2037f]    442     277

EE520   [3f7cf fe740 2037f]    2500    277

EE576   [7ef9f f8501 433fe]    2140    277

EE581   [7df3e e761c 2403fe]   5606    277

EE630   [77cfa df1bf 2e67d0]   2334    277

EE677   [6f9f4 1e03fe 8c740]   1278    277

EE685   [6f9f4 79ff4 804df]    551     277

EE700   [6f9f4 7cfa0 204df]    849     277

EE703   [6f9f4 7cfa0 1f6ff]    692     277

EE709   [6f9f4 79740 3e3fe]    867     277

EE727   [5f3e9 1bf4df 17a0]    3309    277

EE736   [5f3e9 1df1bf 38d740]  2395    277

EE747   [5f3e9 1df5ff 127d0]   3307    277

EE761   [5f3e9 1f97f4 4037f]   614     277

EE769   [5f3e9 1f8fe8 3e3fe]   2763    277

EE775   [5f3e9 1f17d0 7c3fe]   2294    277

EE776   [5f3e9 1f97a0 614df]   3685    277

EE780   [5f3e9 1f97a0 7c5ff]   2700    277

EE782   [5f3e9 1f9740 204df]   1468    277

EE815   [3e7d3 1df1bf 11a680]  1260    277

EE826   [3e7d3 823fe 1b4787]   2365    277

EE839   [3e7d3 f17d0 3e3fe]    2374    277

EE872   [7cfa7 1df1bf 34501]   826     277

EE873   [7cfa7 9f37f 148740]   1525    277

EE876   [7cfa7 1df37f 10404]   1466    277

EE887   [7cfa7 1c13fe 36501]   2976    277

EE888   [7cfa7 1c13fe 6c404]   5314    277

EE890   [7cfa7 cd7a0 1011bf]   4642    277

EE926   [79f4f 82ffd 2d8202]   1868    277

EE933   [79f4f b680 2411bf]    2067    277

EE934   [79f4f 88680 27d3fe]   1814    277

EE936   [79f4f cb501 8237f]    1247    277

EE987   [4fa7d 1f7ffd 280012]  3121    277