MikeMirzayanov

Можно так. Работает для всех m от 1 до MOD-1. Если не хватает, то можно либо увеличить константы (тогда может вырасти длина), либо чуток адаптировать алгоритм. Я подогнал, чтобы было как в примере 6 знаков в коде. На самом деле можно все делать в 64-битных переменных, просто так на Java удобнее.

    private static final BigInteger MULTIPLIER = BigInteger.valueOf(13L);
    private static final BigInteger MOD = BigInteger.valueOf(99990001L);
    private static final BigInteger ADDEND = BigInteger.valueOf(699930007L);

    public static String encode(long m) {
        if (m <= 0 || m >= MOD.longValue()) {
            throw new IllegalArgumentException("Argument is out of range.");
        }
        return BigInteger.valueOf(m).modInverse(MOD).multiply(MULTIPLIER)
                .add(ADDEND).toString(36).toUpperCase();
    }

    public static long decode(String encoded) {
        return new BigInteger(encoded.toLowerCase(), 36).subtract(ADDEND).divide(MULTIPLIER)
                .modInverse(MOD).longValue();
    }

Вот примеры того, что получается (для разных m):

1 BKPXGK
2 MBOAIK
3 PWNQV8
4 RP5H1K
5 SRUICK
10000 X2JV9T
10001 PWMTFN
10002 U025II
10003 TRK6AU
10004 JRJEMK
10005 UARMRU
10006 S2NCNJ
10007 R1E1UK
10008 HRCMBX
10009 WU4GN7
99989996 FVI2O7
99989997 GY73Z7
99989998 IQOU5J
99989999 MBOAI7
99990000 X2MNK7