Da última vez, mostramos como você pode tomar qualquer dois inteiros positivos coprimos e calcular um terceiro inteiro positivo com a propriedade que e, portanto, isso para qualquer inteiro positivo. Ou seja, sempre existe um “inverso multiplicativo”, que “desfaz” os resultados da multiplicação por módulo. Isso é muito legal, mas de que adianta?

Bem, aqui está uma pergunta que eu ocasionalmente recebo:xmy(x * y) % m == 1(x * z * y) % m == z % m zxm

Meu serviço tem uma matriz de n objetos, obviamente indexados de 0 a n-1, cada um dos quais contém o estado que é relevante para algum cliente. Não quero passar o objeto diretamente para o cliente; em vez disso, quero dar a eles um token inteiro que eles possam usar para consultar o servidor sobre o estado do objeto. O token óbvio é o índice da matriz, mas estou preocupado que o desenvolvedor do cliente tenha uma dependência injustificada do fato de que o token é um pequeno inteiro, em vez de tratá-lo como um identificador opaco sem sentido. (Observe que estou assumindo que, nesse cenário, o cliente não é ativamente hostil em relação ao servidor, mas sim potencialmente com bugs.) Quero ofuscar o token que passo de volta. Eu poderia gerar uma sequência de números aleatórios únicos e manter um dicionário bidirecional mapeando índices para tokens e vice-versa, mas isso soa como (1) trabalho, e (2) possíveis bugs, e (3) tempo extra e memória.

Ou equivalentemente

Eu emito algumas centenas de faturas por ano, cada uma com um número de fatura. Por várias razões, prefiro não enviar números sequenciais de facturas. (Por exemplo: é muito fácil cometer erros confusos de transposição ou off-by-one com números sequenciais.) Mas ainda assim eu quero ser capaz de classificar facilmente minhas faturas pela ordem real em que elas foram produzidas.

Ou qualquer número de outras declarações equivalentes do problema.

Este problema é facilmente resolvido com inversos multiplicativos. Comece escolhendo um grande número_, muito maior do que o número de tokens que você precisará gerar_. Digamos 1000000000. Agora escolha qualquer numero coprimo para isso; digamos 387420489. Sabemos de relance que esses números são coprimos porque 1000000000 tem apenas fatores que são divisíveis por 2 ou 5, mas um número terminado em um 9 não pode ser divisível por 2 ou 5; números divisíveis por 2 ou 5 terminam em 0, 2, 4, 5, 6 ou 8. Agora calcule o inverso multiplicativo de usar nossa grande biblioteca inteira, que acaba sendo 513180409.mxx

Agora estamos prontos. Codificamos os números de 0 a n-1 via:

Integer encoded = invoiceNumber * i387420489 % i1000000000;

Isso nos dá um número único de aparência aleatória entre 0 e 999999999. Sabemos que o número será diferente para cada entrada.

Nós o decodificamos com o inverso:

Integer decoded = encoded * i513180409 % i1000000000;

Muito limpo, e muito barato. Não criptograficamente forte, mas quaisquer dois tokens sequenciais parecem muito diferentes um do outro.

Artigo Original