Why does Base58 WIF-format of PK have '5' prefix (the standpoint of mathematics)

Question

I'm trying create raw private keys using the steps:

1. Take a version of PK (0x80) and concatenate (as prefix)with my pseudo-random 32bytes-array.
2. Take a calculated checksum (4bytes) and push it to the end of the array.

3. Encode the result to Base58Check using the algorithm:

   code_string = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
   x = converted_arrayofbytes_to_big_integer;       
   output_string = "";        
   while(x > 0) 
   {
       (x, remainder) = divide(x, 58); //x becomes the integer part of dividing here
       output_string.append(code_string[remainder])
   } 
   return  output_string.Reverse();
   

Ok, I have done it, but I can't understand when x devided into 58 (through the loop) why the last remainder is 4 always (decimal: when the remainder is 4, it use as index of code_string: the last value of output_string is 5 (Base58) therefore)? I assume this's beacause of version's prefix but who can explain it from the standpoint of mathematics?

Answer 1

Mathematically, the thing to understand here is that base58 is similar to any other counting system, base 10 for example. They are both just a way of representing arbitrarily high numbers. The difference is just the characters used.

With counting in base ten, for example, when you get to 9, you start using the next available place holder, and you get 10. In base 58, when you get to z (57), you start using the next available place holder, and you get 21 (weird, I know, it's because 2 in base 58 is like 1 in base 10, and 1 in base 58 is like 0 in base 10).

The point here is that as you count up with the bytes that you are encoding, the base58 value counts up as well. Take this for example:

0x2220 -> 3bd base 58
0x2221 -> 3be base 58
0x2222 -> 3bf base 58
...

Now let's look at the actual data we're encoding with the private key. It consists of 1 version byte (0x80), 32 private key bytes, and 4 checksum bytes, which comes to a total of 37 bytes. Now take the smallest possible 37 byte bit string (which begins with 80):

80000000000000000000000000000000000000000000000000000000000000000000000000

When that is base 58 encoded, you get:

5HpHagT65TZzG1PH3CSu63k8DbpvD8s5ip4nEB3kEsreAbmahZy

And take the largest possible 37 bit string (which begins with 80):

80ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

Which base 58 encodes to:

5Km2kuu7vtFDPpxywn4u3NLu8iSdrqhxWT8tUKjeEXs2fDqZ9iN

And since all private key encodings will fall in the range between 80000000000000000000000000000000000000000000000000000000000000000000000000 and 80ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff, all private key encodings will end up with a 5 at their beginning, just based on how counting in base 58 works!