Here is the fixed decode:
Base58Decode[x_String] :=
FromDigits[
First[First[
StringPosition[
"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz", \
#] - 1]] & /@ Characters[x], 58]
You can test these functions with:
ParallelDo[i = RandomInteger[2^256];
If[i != Base58Decode[Base58Encode[i]], Print[False]], {100000}]
and
Table[{i, Base58Encode[i, n -> 5], Base58Decode[Base58Encode[i]]}, {i,
0, 100}] // TableForm