Matematyka.pl

Rozważmy:

\(\displaystyle{ w = x \cdot k \mod 2^{n}}\)

Na podstawie \(\displaystyle{ w}\) oraz \(\displaystyle{ k}\) mamy znaleźć \(\displaystyle{ x}\). Jeżeli \(\displaystyle{ x}\) oraz \(\displaystyle{ k}\) są nieparzyste, rozwiązanie zawsze istnieje. A co, jeżeli \(\displaystyle{ x}\) lub \(\displaystyle{ k}\) jest parzyste albo, gdy \(\displaystyle{ x}\) i \(\displaystyle{ k}\) są parzyste?

Wówczas zdaje się rozwiązań nie ma? A, jeżeli nie ma to, czy najlepsze co możemy zrobić to zgadywać (może możemy analitycznie znaleźć chociaż część bitów faktycznego rozwiązania, choć z tego co widzę, to chyba nie)? Oraz, czy mamy takie same szanse, że każdy wynik będzie tak samo prawdopodobny? W przypadku mnożenia w ciałach Galois, jeżeli jeden z czynników nie jest zerem, a drugi ma jednostajny rozkład (uniformly distributed, to chyba to samo?), wówczas wynik również będzie miał rozkład jednostajny. Tak nie jest w przypadku mnożenia modulo potęga dwójki. Więc w tym przypadku zdaje się, nie wszystkie wyniki będą tak samo prawdopodobne, gdy spróbujemy zgadywać.

Bez zmniejszania ogólności \(\displaystyle{ 0 < k \le 2^n}\) i \(\displaystyle{ 0 \le w < 2^n}\). Niech \(\displaystyle{ k = 2^{\alpha} \cdot s}\), gdzie \(\displaystyle{ \alpha \in \mathbb{N}}\) i \(\displaystyle{ s}\) jest nieparzyste. Skoro \(\displaystyle{ s}\) jest odwracalne \(\displaystyle{ \bmod{2^n}}\), to

\(\displaystyle{ \{ x \cdot k \bmod{2^n} : x \in \ZZ \} = \{ x \cdot 2^{\alpha} \bmod{2^n} : x \in \ZZ \}}\).

Równanie ma rozwiązanie dokładnie gdy \(\displaystyle{ w}\) należy do tego zbioru, czyli gdy \(\displaystyle{ 2^{\alpha} \mid w}\).

Dasio11 pisze: ↑25 wrz 2022, o 10:23 Bez zmniejszania ogólności \(\displaystyle{ 0 < k \le 2^n}\) i \(\displaystyle{ 0 \le w < 2^n}\). Niech \(\displaystyle{ k = 2^{\alpha} \cdot s}\), gdzie \(\displaystyle{ \alpha \in \mathbb{N}}\) i \(\displaystyle{ s}\) jest nieparzyste. Skoro \(\displaystyle{ s}\) jest odwracalne \(\displaystyle{ \bmod{2^n}}\), to

\(\displaystyle{ \{ x \cdot k \bmod{2^n} : x \in \ZZ \} = \{ x \cdot 2^{\alpha} \bmod{2^n} : x \in \ZZ \}}\).

Równanie ma rozwiązanie dokładnie gdy \(\displaystyle{ w}\) należy do tego zbioru, czyli gdy \(\displaystyle{ 2^{\alpha} \mid w}\).

Dasio11 pisze: ↑25 wrz 2022, o 10:23
\(\displaystyle{ \{ x \cdot k \bmod{2^n} : x \in \ZZ \} = \{ x \cdot 2^{\alpha} \bmod{2^n} : x \in \ZZ \}}\).

To mi się nie zgadza. Niech \(\displaystyle{ n=10}\), \(\displaystyle{ k=7 \cdot 4}\).

\(\displaystyle{ 133 \cdot 28 \bmod{2^{10}} \neq 133 \cdot 4 \bmod{2^{10}}}\)

Dasio11 pisze: ↑25 wrz 2022, o 10:23Równanie ma rozwiązanie dokładnie gdy \(\displaystyle{ w}\) należy do tego zbioru, czyli gdy \(\displaystyle{ 2^{\alpha} \mid w}\).

A kiedy \(\displaystyle{ w}\) należy do tego zbioru? I o jaki zbiór chodzi? Abstrahując, wychodzi mi, że mając \(\displaystyle{ w}\) oraz \(\displaystyle{ k}\) takie, że:

\(\displaystyle{ w = x \cdot k \mod 2^{n}}\)

Jeśli \(\displaystyle{ k}\) jest parzyste, to zawsze znajdziemy \(\displaystyle{ x}\).


Swoją drogą właściwie zadałem nieodpowiednie pytanie. Bo problem z którym faktycznie się zetknąłem, to coś odwrotnego. Mianowicie zakładamy, że istnieje jakieś \(\displaystyle{ x}\), \(\displaystyle{ w}\) oraz \(\displaystyle{ k}\), które spełniają równanie:

\(\displaystyle{ x \cdot k \equiv w \mod 2^{n}}\)

Ktoś ujawnia nam \(\displaystyle{ w}\) oraz \(\displaystyle{ k}\). A my chcemy znaleźć jeszcze \(\displaystyle{ x}\), rozszerzonym algorytmem Euklidesa. Rozwiazujemy więc (\(\displaystyle{ u}\) to niewiadoma):

\(\displaystyle{ u \cdot k \equiv w \mod 2^{n}}\)

Ale okazuje się, że nie zawsze znajdziemy takie \(\displaystyle{ u}\), że:

\(\displaystyle{ u \cdot k \equiv w \mod 2^{n}}\)

To zachodzi zdaje się zawsze, gdy \(\displaystyle{ k}\) jest nieparzyste. Ale co, gdy \(\displaystyle{ k}\) jest parzyste? Przykład:

\(\displaystyle{ 333 \cdot 104 \equiv 840 \mod 1024}\)

Ale rozwiązanie:

\(\displaystyle{ u \cdot 104 \equiv 840 \mod 2^{n}}\)

To \(\displaystyle{ u=77}\). Co więcej liczby \(\displaystyle{ x}\) i \(\displaystyle{ u}\) mają takie same \(\displaystyle{ 4}\) pierwsze bity. To przypadek? Chyba nie, one są identyczne zdaje się w zakresie \(\displaystyle{ log_{2}(s)}\), gdzie \(\displaystyle{ k = s \cdot 2^{\alpha}}\). Trochę już sam sobie odpowiedziałem. W takim przypadku, żeby to odwrócić, musimy zatem zgadnąć \(\displaystyle{ 2^{n}-log_{2}(s)}\) bitów.

Inna sprawa, że nie mam dowodów na poparcie tego, co napisałem. Nie wiem też, czy to jest prawdą, gdy \(\displaystyle{ x}\) również jest nieparzyste albo, czy coś innego nie dzieje się gdy \(\displaystyle{ x = r \cdot 2^{\beta}}\) oraz \(\displaystyle{ k = s \cdot 2^{\alpha}}\) i \(\displaystyle{ \beta \ge \alpha}\).

A czasami dostaniemy właściwe rozwiązanie, jak w przypadku:

\(\displaystyle{ 97 \cdot 40 \equiv 808 \mod 1024}\)

Bo rozwiązanie:

\(\displaystyle{ u \cdot 40 \equiv 808 \mod 1024}\)

to jest \(\displaystyle{ u = 97}\). Nie rozumiem co tu się dzieje i od czego to zależy.

matemix pisze: ↑26 wrz 2022, o 02:15

Dasio11 pisze: ↑25 wrz 2022, o 10:23
\(\displaystyle{ \{ x \cdot k \bmod{2^n} : x \in \ZZ \} = \{ x \cdot 2^{\alpha} \bmod{2^n} : x \in \ZZ \}}\).

To mi się nie zgadza. Niech \(\displaystyle{ n=10}\), \(\displaystyle{ k=7 \cdot 4}\).

\(\displaystyle{ 133 \cdot 28 \bmod{2^{10}} \neq 133 \cdot 4 \bmod{2^{10}}}\)

Równe są nie liczby, tylko zbiory:

\(\displaystyle{ \{ x \cdot 28 \bmod{2^{10}} : x \in \mathbb{Z} \} = \{ x \cdot 4 \bmod{2^{10}} : x \in \mathbb{Z} \} = \{ 0, 4, 8, 12, \ldots, 1020 \}}\).

matemix pisze: ↑26 wrz 2022, o 02:15

Dasio11 pisze: ↑25 wrz 2022, o 10:23Równanie ma rozwiązanie dokładnie gdy \(\displaystyle{ w}\) należy do tego zbioru, czyli gdy \(\displaystyle{ 2^{\alpha} \mid w}\).

A kiedy \(\displaystyle{ w}\) należy do tego zbioru? I o jaki zbiór chodzi?

Chodzi o zbiór napisany w poprzedniej linijce:

\(\displaystyle{ \{ x \cdot 2^{\alpha} \bmod{2^n} : x \in \mathbb{Z} \}}\)

i \(\displaystyle{ w}\) należy do niego dokładnie wtedy, gdy \(\displaystyle{ 2^{\alpha} \mid w}\). Jeśli nie spotkałeś się z taką notacją przy definiowaniu zbiorów, to w tym przypadku

\(\displaystyle{ \{ x \cdot 2^{\alpha} \bmod{2^n} : x \in \mathbb{Z} \} = \{ 0, 2^{\alpha}, 2 \cdot 2^{\alpha}, 3 \cdot 2^{\alpha}, \ldots, 2^n - 2^{\alpha} \}}\).

matemix pisze: ↑26 wrz 2022, o 02:15Abstrahując, wychodzi mi, że mając \(\displaystyle{ w}\) oraz \(\displaystyle{ k}\) takie, że:

\(\displaystyle{ w = x \cdot k \mod 2^{n}}\)

Jeśli \(\displaystyle{ k}\) jest parzyste, to zawsze znajdziemy \(\displaystyle{ x}\).

Raczej: jeśli \(\displaystyle{ k}\) jest nieparzyste.

matemix pisze: ↑26 wrz 2022, o 02:15Ale co, gdy \(\displaystyle{ k}\) jest parzyste?

Przecież już napisałem - ale ok, spróbuję jaśniej. Żeby się dowiedzieć, czy dla danych \(\displaystyle{ w, k \in \mathbb{Z}}\) równanie

\(\displaystyle{ w \equiv x \cdot k \pmod{2^n}}\)

ma rozwiązanie \(\displaystyle{ x \in \mathbb{Z}}\), należy:

1. Znaleźć \(\displaystyle{ w', k' \in \mathbb{Z}}\) przystające \(\displaystyle{ \bmod{2^n}}\) do \(\displaystyle{ w, k}\) odpowiednio, i takie że \(\displaystyle{ 0 \le w' < 2^n}\), \(\displaystyle{ 0 < k' \le 2^n}\);

2. Zapisać \(\displaystyle{ k'}\) w postaci \(\displaystyle{ k' = 2^{\alpha} \cdot s}\), gdzie \(\displaystyle{ \alpha \in \mathbb{N}}\) i \(\displaystyle{ s}\) jest nieparzyste;

3. Sprawdzić, czy \(\displaystyle{ 2^{\alpha}}\) jest dzielnikiem \(\displaystyle{ w'}\).

Jeśli odpowiedź z punktu 3. jest twierdząca, to równanie ma rozwiązanie, a jak jest przecząca, to nie ma. W Twoim przykładzie:

\(\displaystyle{ 840 \equiv x \cdot 104 \pmod{1024}}\)

1. Nierówności \(\displaystyle{ 0 \le 840 < 1024}\) i \(\displaystyle{ 0 < 104 \le 1024}\) już są spełnione.

2. Zapisujemy \(\displaystyle{ 104 = 8 \cdot 13}\).

3. Sprawdzamy, że \(\displaystyle{ 8}\) jest dzielnikiem \(\displaystyle{ 840}\).

Zatem równianie ma rozwiązanie.

matemix pisze: ↑26 wrz 2022, o 02:15Co więcej liczby \(\displaystyle{ x}\) i \(\displaystyle{ u}\) mają takie same \(\displaystyle{ 4}\) pierwsze bity. To przypadek?

W opisanej sytuacji jeśli \(\displaystyle{ x_0}\) jest jakimkolwiek rozwiązaniem, to wszystkie inne rozwiązania to dokładnie liczby \(\displaystyle{ x \in \ZZ}\) spełniające

\(\displaystyle{ x \equiv x_0 \pmod{2^{n-\alpha}}}\)

czyli inaczej mówiąc, liczby "zgadzające się z \(\displaystyle{ x_0}\) na \(\displaystyle{ n-\alpha}\) ostatnich bitach".

Znów w Twoim przykładzie: jednym z rozwiązań jest \(\displaystyle{ x_0 = 333}\), a \(\displaystyle{ 2^{n-\alpha} = 2^{10-3} = 128}\) więc wszystkie rozwiązania to liczby \(\displaystyle{ x \in \ZZ}\) spełniające \(\displaystyle{ x \equiv 333 \pmod{128}}\). Wśród liczb dodatnich są to zatem: \(\displaystyle{ 77, 205, 333, 461, 589, \ldots}\), czyli liczby, których ostatnich siedem bitów to \(\displaystyle{ 1001101}\).

W skrócie, mamy takie przypadki:

• Jeśli \(n=0\) to równość jest spełniona zawsze. Dalej zakładam \(n>0\).
• Jeśli \(2\not\mid k\), to algorytmem Euklidesa znajdujemy liczbę odwrotną do \(k\) modulo \(2^n\) i mnożymy przez nią równanie stronami. Na przykład równanie
  \(5 \equiv 3x \pmod{16}\)
  mnożymy przez \(11\) dostając
  \(7 \equiv x \pmod{16}\).
• Jeśli \(2\mid k\), ale \(2\not\mid w\), to nie ma rozwiązań, bo liczba parzysta nie może być równa nieparzystej.
• Jeśli \(2\mid k\) i \(2\mid w\), to możemy zmniejszyć wykładnik dwójki o jeden, na przykład równanie
  \(10 \equiv 6x\pmod{32}\)
  zamieniamy na
  \(5 \equiv 3x \pmod{16}\).

Ok, chyba już rozumiem. Czyli tutaj:

matemix pisze: ↑26 wrz 2022, o 02:56 A czasami dostaniemy właściwe rozwiązanie, jak w przypadku:

\(\displaystyle{ 97 \cdot 40 \equiv 808 \mod 1024}\)

Bo rozwiązanie:

\(\displaystyle{ u \cdot 40 \equiv 808 \mod 1024}\)

to jest \(\displaystyle{ u = 97}\). Nie rozumiem co tu się dzieje i od czego to zależy.

Po prostu trafiłem na właściwie rozwiązanie przypadkowo, a właściwie to przypadkowo wybrałem sobie takie pierwsze równanie:

\(\displaystyle{ 97 \cdot 40 \equiv 808 \mod 1024}\)

że później można było to odwrócić. Gdybym wybrał sobie inne rozwiązanie spełniające \(\displaystyle{ x \equiv 97 \mod 128}\), np.:

\(\displaystyle{ 353 \cdot 40 \equiv 808 \mod 1024}\)

To nie odwrócę tego właściwie. Teraz mogę nawet oszacować jak często losując sobie dwie liczby 10-bitowe \(\displaystyle{ x}\) oraz \(\displaystyle{ k}\), odwrócę to później właściwie (gdzie ujawniamy komuś później tylko \(\displaystyle{ w}\) i \(\displaystyle{ k}\)), jak często nie i ile średnio bitów trzeba zgadnąć w takim procesie. Dzięki