Finding The Inverse of The Modulo Operation

Question

I created an algorithm to convert a hexadecimal digit into an alphanumeric string, but now I want to create the inverse of this algorithm. The algorithm, in short, is as follows:

hexadecimal digit % length of alphanumeric character array = index in alphanumeric character array

For example, the algorithm takes hex digit 4e (78 in decimal), mods it with the size of an alphanumeric character array (size: 62), and returns decimal number 16, which is a G. The alphanumeric character array in this example is structured like the following: (0-9, A-Z, a-z).

In short this example is written as: (4e)78 % 62 = 16(G)

The inverse of this algorithm is what I hope to achieve and from various tests, it seems multiple results can occur, but my ultimate goal is to end up with a reversible algorithm, where, for example, hexadecimal digit 4e gets converted to letter G then back again to 4e when put through the inverse algorithm. From the example, I developed a possible description of the inverse algorithm:

Suppose we have a modular equation. Let x be the dividend, y be the divisor, and r be the remainder. r and y are given where r=16 and y=62. Find an x such that x % y = r or x % 62 = 16.

The solution that I tried: Bruteforce the dividend

The dividend will never be out of the closed interval [0, 255] since a pair of hexadecimal numbers can have a maximum value of ff, which is 255 in decimal. Thus, if we test x's against the modular equation until we get an equal remainder, we can derive the dividend.

However, this solution will result in multiple possible x values due to the modulo operation causing a wrap-around effect in the alphanumeric array, which means multiple values can cause the equation to hold true. In the case of the provided example, the proposed solution results in the following dividends: 16, 78, 140, and 202. The second dividend is the correct one and the one that results in the algorithms being reversible. However, the issue is finding it, since the correct one isn't directly known at the time of running the inverse algorithm.

Any help in devising either a solution to my proposed method or a different one would be greatly appreciated. Thanks.

Answer 1

I ended up solving my issue, but not in the way I expected. The solution involves the inherent halving of the output string. Using this, one can simply calculate the quotient of dividing x by y and using that as the second alphanumeric character, forming a pair. In the given example, the resulting G would become G1 because the modular arithmetic involved looping over the alphanumeric character array once.

The algorithm is now as follows: x % y = r + (x / y), which is easily reversible by bruteforcing the possible dividends and simply selecting the correct one using the second character in the alphanumeric pair. Thus, this modified algorithm is now reversible and has been proven to work with the example given in the original question.