Jeżeli weźmiemy sobie liczby \(\displaystyle{ L}\) od \(\displaystyle{ 1}\) do \(\displaystyle{ 2^{n}-1}\) i policzymy:
\(\displaystyle{ z = (2^{n}-L) \cdot k \mod 2^{n}}\)
dla jakiegoś nieparzystego \(\displaystyle{ k}\) od \(\displaystyle{ 1}\) do \(\displaystyle{ 2^{n}-1}\), to zawsze istnieje takie \(\displaystyle{ a}\), że:
\(\displaystyle{ a \cdot z = L}\)
czyli, że mnożąc nasze \(\displaystyle{ z}\) przez tę liczbę dostaniemy nasze \(\displaystyle{ L}\). Tę liczbę \(\displaystyle{ a}\) można wyznaczyć obliczając:
\(\displaystyle{ 1 = (2^{n}-L) \cdot k \mod 2^{n}}\)
Należy znaleźć taką liczbę \(\displaystyle{ L}\), że przy wybranym \(\displaystyle{ k}\) dostaniemy \(\displaystyle{ 1}\).
Przykład:
Niech \(\displaystyle{ k=11}\) i \(\displaystyle{ n=4}\). Wówczas możemy policzyć powiedzmy dla \(\displaystyle{ L=5}\):
\(\displaystyle{ z = (16-5) \cdot 11 \mod 16}\)
\(\displaystyle{ z=9}\)
\(\displaystyle{ a}\) będzie wynosić \(\displaystyle{ 13}\). I faktycznie wówczas \(\displaystyle{ 13 \cdot 9 \mod 16 = 5}\).
Jak udowodnić, że zawsze będzie istniało takie \(\displaystyle{ a}\), że używając go możemy łatwo znaleźć \(\displaystyle{ L}\), mając \(\displaystyle{ z}\) oraz, że to \(\displaystyle{ a}\) można wyznaczyć rozwiązując \(\displaystyle{ 1 = (2^{n}-L) \cdot k \mod 2^{n}}\)?
Normalnie, żeby przy ustalonym \(\displaystyle{ k}\) oraz zadanym \(\displaystyle{ z}\) wyznaczyć \(\displaystyle{ L}\), musielibyśmy rozwiązać:
\(\displaystyle{ 9 = (16-L) \cdot 11 \mod 16 }\)
Ale istnieje przedstawiony, szybszy sposób.