I have a 64-bit number ($x$) that I want to programmatically display as base 58. I have currently found two solutions, the first one is the double dabble and the second one is mod-and-divide.
I'm working in JavaScript (the 64-bit integer is stored as a buffer) and I can apply logic gates on a maximum of 32 bits. Therefore, I had to exclude the double dabble one.
The mod-and-divide method requires applying % 58.
I wanted to speed up the process, but I'm still trying to figure some stuff out.
I first considered converting from base 29 to base 58 (base 29 may be easily calculated with n.toString(29)).
Please note that:
- $b$ is a binary digit
- $c$ is a base 29 digit
- $d$ is a base 58 digit
$$\sum_{i=0}^n 58^i d_i = \sum_{i=0}^n 29^i 2^i d_i = \sum_{i=0}^n 29^i c_i$$
Hence, $c_i = 2^i \cdot d_i$.
My first question is: can I use this method programmatically to quickly convert from base 29 to base 58? As far as I can see, using a carry should be enough, but I wanted to make sure there aren't better ways to do it. I think that $2x ≡ 2y$ $($mod $58)$ becoming $x ≡ y$ $($mod $29)$ could help.
I then considered using Fermat's little theorem to quickly compute % 29: $a^{28}$ $≡$ $1 ($mod $29)$.
$2^{28} ≡ 1$ $($mod $29)\Rightarrow2^{28+k} ≡ 2^{28}\cdot2^k ≡ 2^k$ $($mod $29)$
In "English" it means that we can simply create chunks of 28 bits starting from the Least Significant Bit; then thanks to the sum properties of modular arithmetic, we can mod the single chunks and mod the sum of these results:
| \ | $chunk_2$ | $chunk_1$ | $chunk_0$ |
|---|---|---|---|
| starting bit | 56 | 28 | 0 |
| ending bit | 63 | 55 | 27 |
We can do: $x ≡ (chunk_2$ mod $29)+(chunk_2$ mod $29)+(chunk_1$ mod $29) ≡ y$ $($mod $29)$
Now, my second question is: is there some simple way to apply mod 29 on a 28 bit integer?
I feel like there won't be any real gain by using a different method other than a simple chunk[i]%29, but I hope someone could help me achieve binary to base 58.