Formula from pattern of numbers

[Guest]

I am trying to understand how this 2 table are created mathematically and how the formula would look alike.
Can anybody look into this and show me how it is done?

0 0 0
1 C1 C0
2 81 C1
3 40 1
4 1 C3
5 C0 3
6 80 2
7 41 C2
8 1 C6
9 C0 6
10 80 7
11 41 C7
12 0 5
13 C1 C5
14 81 C4
15 40 4
16 1 CC
17 C0 0C
18 80 0D
19 41 CD
20 0 0F
21 C1 CF
22 81 CE
23 40 0E
24 0 0A
25 C1 CA
26 81 CB
27 40 0B
28 1 C9
29 C0 9
30 80 8
31 41 C8
32 1 D8
33 C0 18
34 80 19
35 41 D9
36 0 1B
37 C1 DB
38 81 DA
39 40 1A
40 0 1E
41 C1 DE
42 81 DF
43 40 1F
44 1 DD
45 C0 1D
46 80 1C
47 41 DC
48 0 14
49 C1 D4
50 81 D5
51 40 15
52 1 D7
53 C0 17
54 80 16
55 41 D6
56 1 D2
57 C0 12
58 80 13
59 41 D3
60 0 11
61 C1 D1
62 81 D0
63 40 10
64 1 F0
65 C0 30
66 80 31
67 41 F1
68 0 33
69 C1 F3
70 81 F2
71 40 32
72 0 36
73 C1 F6
74 81 F7
75 40 37
76 1 F5
77 C0 35
78 80 34
79 41 F4
80 0 3C
81 C1 FC
82 81 FD
83 40 3D
84 1 FF
85 C0 3F
86 80 3E
87 41 FE
88 1 FA
89 C0 3A
90 80 3B
91 41 FB
92 0 39
93 C1 F9
94 81 F8
95 40 38
96 0 28
97 C1 E8
98 81 E9
99 40 29
100 1 EB
101 C0 2B
102 80 2A
103 41 EA
104 1 EE
105 C0 2E
106 80 2F
107 41 EF
108 0 2D
109 C1 ED
110 81 EC
111 40 2C
112 1 E4
113 C0 24
114 80 25
115 41 E5
116 0 27
117 C1 E7
118 81 E6
119 40 26
120 0 22
121 C1 E2
122 81 E3
123 40 23
124 1 E1
125 C0 21
126 80 20
127 41 E0
128 1 A0
129 C0 60
130 80 61
131 41 A1
132 0 63
133 C1 A3
134 81 A2
135 40 62
136 0 66
137 C1 A6
138 81 A7
139 40 67
140 1 A5
141 C0 65
142 80 64
143 41 A4
144 0 6C
145 C1 AC
146 81 AD
147 40 6D
148 1 AF
149 C0 6F
150 80 6E
151 41 AE
152 1 AA
153 C0 6A
154 80 6B
155 41 AB
156 0 69
157 C1 A9
158 81 A8
159 40 68
160 0 78
161 C1 B8
162 81 B9
163 40 79
164 1 BB
165 C0 7B
166 80 7A
167 41 BA
168 1 BE
169 C0 7E
170 80 7F
171 41 BF
172 0 7D
173 C1 BD
174 81 BC
175 40 7C
176 1 B4
177 C0 74
178 80 75
179 41 B5
180 0 77
181 C1 B7
182 81 B6
183 40 76
184 0 72
185 C1 B2
186 81 B3
187 40 73
188 1 B1
189 C0 71
190 80 70
191 41 B0
192 0 50
193 C1 90
194 81 91
195 40 51
196 1 93
197 C0 53
198 80 52
199 41 92
200 1 96
201 C0 56
202 80 57
203 41 97
204 0 55
205 C1 95
206 81 94
207 40 54
208 1 9C
209 C0 5C
210 80 5D
211 41 9D
212 0 5F
213 C1 9F
214 81 9E
215 40 5E
216 0 5A
217 C1 9A
218 81 9B
219 40 5B
220 1 99
221 C0 59
222 80 58
223 41 98
224 1 88
225 C0 48
226 80 49
227 41 89
228 0 4B
229 C1 8B
230 81 8A
231 40 4A
232 0 4E
233 C1 8E
234 81 8F
235 40 4F
236 1 8D
237 C0 4D
238 80 4C
239 41 8C
240 0 44
241 C1 84
242 81 85
243 40 45
244 1 87
245 C0 47
246 80 46
247 41 86
248 1 82
249 C0 42
250 80 43
251 41 83
252 0 41
253 C1 81
254 81 80
255 40 40

[Guest]

The table can be created by applying the binary operator XOR, bit shifts, and binary rotations to the row number.

Specifically if the row is [tex]n[/tex] (starting from row [tex]0[/tex]), the entry for row [tex]n[/tex] is a 4 digit hexadecimal number.
This number can be calculated by:
First XOR all the individual bits of [tex]n[/tex] when written in binary, call this the [tex]p(n)[/tex] (the parity).
Multiply [tex]p(n)[/tex] by 7.
Left shift the result by 8 bits.
Bitwise XOR the result with [tex]n[/tex] (pad with zeros where necessary).
Bitwise XOR the result with [tex]2n[/tex] (or equivalently [tex]n[/tex] left shifted by 1 bit).
Left Rotate the result in binary by 2 bits (assume the length of the result is 16 bits, pad with zeros where necessary).

As an example take [tex]n=107[/tex].
In binary [tex]n=1101011[/tex].
[tex]p(107) = 1\oplus 1\oplus 0\oplus 1\oplus 0\oplus 1\oplus 1 = 1[/tex].
[tex]7p(107) = 7[/tex] in decimal [tex]=111[/tex] in binary.
Left shifting by 8 bits gives [tex]11100000000[/tex] in binary.
XOR with [tex]n[/tex] gives [tex]11100000000\oplus 00001101011 = 11101101011[/tex].
XOR with [tex]2n[/tex] gives [tex]11101101011\oplus 00011010110 = 11110111101[/tex].
Left Rotate by 2 bits
[tex]11110111101\rightarrow 0000011110111101[/tex] (pad with zeros to make it 16 bits)
[tex]\rightarrow \left[00000111101111\right]\left[01\right] \rightarrow \left[01\right]\left[00000111101111\right][/tex] (rotate by 2 bits)
[tex]\rightarrow 0100000111101111[/tex]
Convert to hexadecimal digits
[tex]\left[0100\right]\left[0001\right]\left[1110\right]\left[1111\right][/tex] (split into groups of 4)
[tex]\left[4\right]\left[1\right]\left[14\right]\left[15\right][/tex] (in decimal)
41EF (in hexadecimal).

A small C++ program that generates the table can be found at
http://cpp.sh/3tqt
(no need to download or install anything, the website has a Run button which will execute the code).

Hope this helped,

R. Baber.

[Guest]

Thank you very much!
I am not very strong in math but can you possible show me this in Visual Basic 6?

[Guest]

I'm afraid I don't have a copy of VB6, I don't really know any visual basic but below is some code that seems to work in VB.Net, you can run it at
https://dotnetfiddle.net/Ir7DxA
Hopefully converting it to VB6 won't be too difficult (you probably just need to change the Console.WriteLine function to Print or something, and change the imports)

Code: Select all

Imports System
Imports Microsoft.VisualBasic
            
Public Module Module1
   'Xor all the binary digits of 'input'.
   Public Function Parity(input As Integer) As Integer
      Dim output As Integer = 0
      While input <> 0
         output = output Xor (input And 1)
         input = input >> 1
      End While
      Return output
   End Function
   
   'Move the 2 least significant bits into the most significant positions.
   'Assume the input is 16 bits long (i.e. 4 hexadecimal digits).
   Public Function LeftRotateBy2(input As Integer) As Integer
      Return ((input And 3)<<14) Or (input>>2)
   End Function
   
   'Convert 'input' into a 4 digit hexadecimal string
   Public Function ConvertToHex(input As Integer) As String
      Dim hexDigits As String = "0123456789ABCDEF"
      Dim output As String = ""
      For i As Integer = 1 To 4
         output = Mid(hexDigits, (input And 15)+1, 1) & output
         input = input >> 4
      Next
      Return output
   End Function
   
   'Create table
   Public Sub Main()
      Dim result As Integer
      For n As Integer = 0 To 255
         result = LeftRotateBy2((Parity(n)*7<<8) Xor n Xor (n<<1))
         'Display result as a 4 digit hexadecimal
         Console.WriteLine("{0,3} : {1}", n, ConvertToHex(result))
      Next
   End Sub
End Module


Hope this helped,

R. Baber.

[Guest]

Out of interest, what is this table for exactly?

R. Baber.

[Guest]

Its possible I will use it for encryption for my project later,

I need to understand it a bit more and the idea was to use each table but not both at same process.
How would I make it as array1 and array2?
I see your comment "Display result as a 4 digit hexadecimal"
How do you do each as 2 digit hexadecimal insted?

[Guest]

It is easy to split a number into two parts using some "bit manipulation", you may want to look up tutorials on this. In particular you can right shift the lower order bits away to get only the high order bits, and if you want the low order bits you can use a mask to throw away the high order bits.
See
https://dotnetfiddle.net/G9hPTn
or below, for updated code

Code: Select all

Imports System
Imports Microsoft.VisualBasic
            
Public Module Module1
   'Xor all the binary digits of 'input'.
   Public Function Parity(input As Integer) As Integer
      Dim output As Integer = 0
      While input <> 0
         output = output Xor (input And 1)
         input = input >> 1
      End While
      Return output
   End Function
   
   'Move the 2 least significant bits into the most significant positions.
   'Assume the input is 16 bits long (i.e. 4 hexadecimal digits).
   Public Function LeftRotateBy2(input As Integer) As Integer
      Return ((input And 3)<<14) Or (input>>2)
   End Function
   
   'Convert 'input' into a 'numDigits' digit hexadecimal string
   Public Function ConvertToHex(input As Integer, numDigits As Integer) As String
      Dim hexDigits As String = "0123456789ABCDEF"
      Dim output As String = ""
      For i As Integer = 1 To numDigits
         output = Mid(hexDigits, (input And 15)+1, 1) & output
         input = input >> 4
      Next
      Return output
   End Function
   
   'Create table
   Public Sub Main()
      Dim result As Integer
      Dim resultHiDigits, resultLoDigits As Integer
      For n As Integer = 0 To 255
         result = LeftRotateBy2((Parity(n)*7<<8) Xor n Xor (n<<1))
         'Split result into two
         resultHiDigits = result>>8
         resultLoDigits = result And 255
         'Display result as two 2 digit hexadecimal numbers
         Console.WriteLine("{0,3} : {1} {2}", n,
            ConvertToHex(resultHiDigits, 2),
            ConvertToHex(resultLoDigits, 2))
      Next
   End Sub
End Module


I would be careful about using these tables for any sort of serious encryption. Designing Substitution Tables a.k.a. S-Boxes, see
https://en.wikipedia.org/wiki/S-box
for encryption seems like a very tricky thing to get right. You are better off using a standard, well established, and thoroughly tested and researched encryption algorithm like AES or one of the runner ups in that competition. If it's just for fun you should be fine, if it's for anything serious, I would urge you to seriously reconsider.

Hope this helped,

R. Baber.

[Guest]

Thank you for the advise I really appreciate your help
This is mostly for fun and for me to learn some

Can you post the c++ part of the this last one too so I have it in both version?

I will try to study this and try to convert it to vb6 and
I may have some more question later if it is ok and when I understand this more

[Guest]

Sure

http://cpp.sh/9rw4

Code: Select all

#include <iostream>
#include <iomanip>

using namespace std;

//Xor all the binary digits of 'input'.
int parity(int input)
{
    int output = 0;
   
    while(input!=0)
    {
        output ^= input&1;
        input >>= 1;
    }
   
    return output;
}

//Move the 2 least significant bits into the most significant positions.
//Assume the input is 16 bits long (i.e. 4 hexadecimal digits).
int leftRotateBy2(int input)
{
    return ((input&3)<<14) | (input>>2);
}

int main()
{
    for(int n=0; n<256; n++)
    {
        int result = leftRotateBy2((parity(n)*7<<8)^n^(n<<1));
       
        //Split the result.
        int resultHiDigits = result >> 8;
        int resultLoDigits = result & 255;
       
        //Display.
        cout << dec << setfill(' '); //Display as a decimal.
        cout << setw(3) << n << " : ";
        cout << hex << setfill('0') << uppercase; //Display as hexadecimal digits.
        cout << setw(2) << resultHiDigits << " ";
        cout << setw(2) << resultLoDigits << endl;
    }
   
    return 0;
}


R. Baber.

[Guest]

Hi again!

I have managed to convert the code to vb6 with help but still its very complicated for me

You do explain very good how the program works in your first post and also very good comment with the code in each post.

Does it still apply everywhere even after we changed the table from 4 digit hexadecimal to 2 digit hexadecimal?

You were very quick to recognize the formula, may I ask what method or procedure do you use to recognize it?

[Guest]

Glad to hear it.

Yes, it still applies everywhere. There is little to no benefit in creating two separate methods for each array, it makes more sense to calculate the 4 digit number first then split it into two.

I'm reasonably good at mathematics, and have spent years doing it, which means I've had plenty of practice in spotting patterns. Here are the things I noticed (in order) which allowed me to deduce the "formula".

1) If you look at the list you notice that there are numbers and letters but the letters don't go past F, which is a clue that you are looking at hexadecimal.

2) Hexadecimal is in some sense a shorthand representation of binary, so this is a clue that you may need to convert things to binary at some point.

3) Some entries are two digits, but some are one. So we probably need to pad the digits to make them all 2 digits.

4) The first digit just cycles through 0,C,8,4 over and over again. A very clear pattern (suggesting that padding one digit numbers with 0 was the right thing to do).

5) In binary 0,C,8,4 is 0000, 1100, 1000, 0100. So the last two bits are always 0, suggesting that if look at other digits in binary maybe they have bits which are always 0 (or 1).

6) The second digit is always 0 or 1, which in binary is 0000, 0001, so the first three bits are always 0.

7) If we consider the first 2 digits as one number we have 5 bits in a row which are always 0. This is a clue that the digits should be considered as one big number (what happens to the bits at the end of one digit, appears to happen at the start of the bits of the next digit).

8 ) The pattern of 0 and 1 in the second digit is complicated. The fact that the first digit cycles every 4 suggests looking at it in groups of 4 might be a good idea.

9) In groups of 4 the second digit looks like 0110, 1001, 1001, 0110, 1001, 0110, ... Clearly there is a pattern, we only ever see groups which look like 0110 or 1001

10) Looking at the first number in every group of 4 we get 0110100110010110... This looks suspiciously like the same pattern as before. We can split it into groups of 4, and look at the first digit.

11) Again we see the same pattern, we can repeat step 10, to see the same pattern appear yet again.

12) Applying a lot of thought, you can deduce what is happening is that 0110 is occurring over and over but is sometimes getting flipped (0 is replaced by 1 and 1 by 0). If it was just 0110 over and over, the value would only depend on the last two binary bits of the row number n, i.e. f(bit 2 of n, bit 1 of n), where f(0,0) = 0, f(0,1) = 1, f(1,0) = 1, f(1,1) = 0. However, f(bit 2, bit 1) gets flipped according to the pattern 0110 1001 1001 0110 ... If this pattern was just 0110 0110 0110 over and over then it could be written as f(bit 4 of n, bit 3 of n). But it isn't 0110 over and over, it is 0110 with some flipping going on, in fact the flipping as you may start to guess depends on f(bit 6, bit 5) and f(bit 8, bit 7). Flipping in binary is often represented by XOR with the symbol [tex]\oplus[/tex]. So the pattern for the second digit is
f(bit 8, bit 7)[tex]\oplus[/tex]f(bit 6, bit 5)[tex]\oplus[/tex]f(bit 4, bit 3)[tex]\oplus[/tex]f(bit 2, bit 1)
At this point you may guess that the function f may actually have a simpler representation, namely XOR, so digit 2 is actually just
bit 8[tex]\oplus[/tex]bit 7[tex]\oplus[/tex]bit 6[tex]\oplus[/tex]bit 5[tex]\oplus[/tex]bit 4[tex]\oplus[/tex]bit 3[tex]\oplus[/tex]bit 2[tex]\oplus[/tex]bit 1
Which I called [tex]p(n)[/tex] in previous posts.
(Note that the group of 4 thing that we started out with was a bit of a red herring, this often happens when investigating maths. Often the guess we started with gets changed/ditched for something better.)

13) Next up is the 3rd digit. You should notice that it seems to be related to the second digit (again suggesting we are looking at one 4 digit number not 4 separate entities).

14) In fact for n between 0 and 31 the third digit matches the second digit with 1 being replaced by C. When n is between 32 and 63 it matches the second digit with 0,1 being replaced by 1,D. We can continue looking at groups of 32 seeing how 0,1 from the second digit gets mapped into the third digit. Clearly we need to investigate what is going on in binary.

15) In binary we see that the highest significant bit of the third digit matches precisely the lowest significant bit of the second digit (more evidence this is one giant 4 digit number).

16) The second highest significant bit of the third digit also appears to be p(n) but it doesn't quite work, it gets flipped when n is between 128 and 255, i.e. it is p(n)[tex]\oplus[/tex]bit 8 of n.

17) The last two bits of the third digit don't appear to have anything to do with p(n) but just keep cycling. They follow the pattern 0110 but stretched out over several rows, then repeated. Given we already know that 0110 is synonymous with XOR, we can guess that the pattern is bit 8 of n[tex]\oplus[/tex] bit 7 of n, and bit 7 of n[tex]\oplus[/tex]bit 6 of n.

18) Finally we look at the fourth digit. Given what we know, we should look at in binary and compare it with patterns we've seen occurring in other digits. It's not particularly difficult to see that the patterns continue and that the bits are computed as bit 6 of n[tex]\oplus[/tex]bit 5, then bit 5[tex]\oplus[/tex]bit 4, bit 4[tex]\oplus[/tex]bit 3, and finally bit 3[tex]\oplus[/tex]bit 2.

19) It seems a bit odd there is not a bit 2[tex]\oplus[/tex]bit 1, but if we revisit the first digit (that cycled 0,C,8,4), we see that the highest significant bit of the first digit is bit 2[tex]\oplus[/tex]bit 1, and the second highest bit is just bit 1 of n. It makes more sense to group these two bits of the first digit with the bits of the last digit.

20) Putting all this together gives us the following formulas for all 16 bits:
Bit 14 = 0
Bit 13 = 0
Bit 12 = 0
Bit 11 = 0
Bit 10 = 0
Bit 9 = p(n)
Bit 8 = p(n)
Bit 7 = p(n)[tex]\oplus[/tex] bit 8 of n
Bit 6 = bit 8 of n [tex]\oplus[/tex] bit 7 of n
Bit 5 = bit 7 of n [tex]\oplus[/tex] bit 6 of n
Bit 4 = bit 6 of n [tex]\oplus[/tex] bit 5 of n
Bit 3 = bit 5 of n [tex]\oplus[/tex] bit 4 of n
Bit 2 = bit 4 of n [tex]\oplus[/tex] bit 3 of n
Bit 1 = bit 3 of n [tex]\oplus[/tex] bit 2 of n
Bit 16 = bit 2 of n [tex]\oplus[/tex] bit 1 of n
Bit 15 = bit 1 of n

21) If you know how to do bit manipulation in programming then it is easy to see that we can get the various terms by doing things like multiplying p(n) by 7 left shifted by 8 (which 11100000000 in binary) to get the p(n) terms for bit 9, 8, and 7. XORing with n gets the left hand part for bits 6,5,4,3,2,1,16,15. XORing with n left shifted by 1, gets the right hand parts for bits 7,6,5,4,3,2,1,16. Then doing a left rotate on the last 2 bits puts bits 16 and 15 in the right place.


As you can see it was all just guessing, rewriting things in binary, trying to come up with patterns (if they don't work trying different ideas, guesses, patterns). It is a lot of hard work, and ultimately requires you to be good at pattern finding, and having knowledge and familiarity of binary. These things can not be taught quickly and easily, you need to do a lot of practising. The more you do the better you'll get, but it could take years. Even for someone like me who happened to spot the patterns quickly and happened to be fairly comfortable with binary and binary manipulations, it is still very time consuming to convert everything and try out patterns. There is no quick and easy magical way to do these things.

In general the pattern may just be too hard to spot, or require maths you are just not familiar with, in which case it will be impossible for you to work out. (If you don't know binary, hexadecimal, or XOR, there is almost no chance you'll spot the pattern in your particular case.) The more you know and the more experienced you are the better your chances, but there is no guarantee you will be able to work out the pattern.

Hopefully I've given you some insight into how to approach and think about these things.

Hope this helped,

R. Baber.

[Guest]

Thank you so much for taking the time to explain this in so great detail,
it will help me to understand this all alot better and I am sure it will help others too.