Inversa modular §

---

Dados inteiros positivos e e sendo , existem multiplicadores e tais que:

1. Escolher aleatoriamente dois números grandes §

Primeiramente, é preciso verificar se os números escolhidos são primo e para isso uma das formas é utilizar o Algoritmo de Euclides.

Q	106	2	9
2023	19	9	1
R	9	1	0

O valor da última coluna à esquerda e da segunda linha representa o mdc (maior divisor comum) dos números escolhidos. Dessa forma, se o então e são primos.

2. Aplicar a relação fundamental da divisão §

Representar as divisões, exceto a última, utilizando o algoritmo da divisão multiplicador (ou Relação Fundamental da Divisão).

3. Isolar o resto e adicionar multiplicadores aos divisores §

4. Substituir na última equações (de baixo para cima) §

A inversa modular de

Referências §

---