• #### PERMPOLYPRNG, a simple PRNG based on permutation polynomials mod 2*

From Bob H@21:1/5 to All on Thu Oct 1 18:57:16 2015
On Thursday, October 1, 2015 at 12:49:43 PM UTC-4, I wrote:
... you create a PRNG by iterating x->f(x) where f(x) is a polynomial mod 2^N with coefficients intended to generate a full cycle ...

Your code appears to be more restrictive than is necessary to ensure full cycle. The function fullperiodcriteria() appears to enforce
c_0 = c_1 = 1 mod 4
c_i = 0 mod 4 for all other i
and cites reference [1] as the reason. However, in Anashin (2004), "Pseudorandom number generation by p-adic ergodic transformations" different, less strict, criteria are given (pg 23, section 3.28, citing a proof by Larin). So while your criteria may
produce a full cycle function, I wonder if whether your restricted set of functions has less variation in the most significant bits than it might otherwise have.

Bob H

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Bob H@21:1/5 to Mok-Kong Shen on Thu Oct 1 09:49:42 2015
On Friday, March 6, 2015 at 9:31:03 AM UTC-5, Mok-Kong Shen wrote:
Python code available at: http://http://s13.zetaboards.com/Crypto/topic/7355166/1/

As best I can tell from the code, you create a PRNG by iterating x->f(x) where f(x) is a polynomial mod 2^N with coefficients intended to generate a full cycle. And I guess you take some number of the most significant bits and xor them with python's
built in PRNG to form your keystream. And there's some mention on Von Neuman bias correction but it's hard to see how that's involved.

I don't know how good you can expect those most significant bits to be. For example, below is the cycle generated by x -> 4x^2 + x + 1 mod 256 (read left-to-right, then top-to-bottom). Stepping down any column represents stepping by 16 iterations in
the sequence. The sequences of most significant 4 bits in any column conform to either "subtract 1" or "add 7". The first two are "subtract 1", the next two are "add 7" and so on.

00 01 06 97 DC 1D 42 53 F8 F9 BE CF 54 95 7A 0B
F0 F1 76 07 CC 0D B2 C3 E8 E9 2E 3F 44 85 EA 7B
E0 E1 E6 77 BC FD 22 33 D8 D9 9E AF 34 75 5A EB
D0 D1 56 E7 AC ED 92 A3 C8 C9 0E 1F 24 65 CA 5B
C0 C1 C6 57 9C DD 02 13 B8 B9 7E 8F 14 55 3A CB
B0 B1 36 C7 8C CD 72 83 A8 A9 EE FF 04 45 AA 3B
A0 A1 A6 37 7C BD E2 F3 98 99 5E 6F F4 35 1A AB
90 91 16 A7 6C AD 52 63 88 89 CE DF E4 25 8A 1B
80 81 86 17 5C 9D C2 D3 78 79 3E 4F D4 15 FA 8B
70 71 F6 87 4C 8D 32 43 68 69 AE BF C4 05 6A FB
60 61 66 F7 3C 7D A2 B3 58 59 1E 2F B4 F5 DA 6B
50 51 D6 67 2C 6D 12 23 48 49 8E 9F A4 E5 4A DB
40 41 46 D7 1C 5D 82 93 38 39 FE 0F 94 D5 BA 4B
30 31 B6 47 0C 4D F2 03 28 29 6E 7F 84 C5 2A BB
20 21 26 B7 FC 3D 62 73 18 19 DE EF 74 B5 9A 2B
10 11 96 27 EC 2D D2 E3 08 09 4E 5F 64 A5 0A 9B

For the more random looking x -> 4x^5 + 5x + 17 mod 256 you get this sequence. The columns again exhibit simple linearity in the most significant bits, although the have more different slopes.

00 11 AA E3 CC 0D C6 6F F8 E9 C2 5B 84 A5 9E A7
70 41 5A 53 BC BD F6 5F 68 19 72 CB 74 55 CE 97
E0 71 0A C3 AC 6D 26 4F D8 49 22 3B 64 05 FE 87
50 A1 BA 33 9C 1D 56 3F 48 79 D2 AB 54 B5 2E 77
C0 D1 6A A3 8C CD 86 2F B8 A9 82 1B 44 65 5E 67
30 01 1A 13 7C 7D B6 1F 28 D9 32 8B 34 15 8E 57
A0 31 CA 83 6C 2D E6 0F 98 09 E2 FB 24 C5 BE 47
10 61 7A F3 5C DD 16 FF 08 39 92 6B 14 75 EE 37
80 91 2A 63 4C 8D 46 EF 78 69 42 DB 04 25 1E 27
F0 C1 DA D3 3C 3D 76 DF E8 99 F2 4B F4 D5 4E 17
60 F1 8A 43 2C ED A6 CF 58 C9 A2 BB E4 85 7E 07
D0 21 3A B3 1C 9D D6 BF C8 F9 52 2B D4 35 AE F7
40 51 EA 23 0C 4D 06 AF 38 29 02 9B C4 E5 DE E7
B0 81 9A 93 FC FD 36 9F A8 59 B2 0B B4 95 0E D7
20 B1 4A 03 EC AD 66 8F 18 89 62 7B A4 45 3E C7
90 E1 FA 73 DC 5D 96 7F 88 B9 12 EB 94 F5 6E B7

By the way, the URL you give as reference [1] only gives the errata for, I presume, the article you intend to link to.

Bob H

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)