Kódování a dekódování čísel pomocí modulární aritmetiky
popř. počítání soustavy rovnic v Calcu pomocí inverzní matice

PhDr. Mgr. Jeroným Klimeš, Ph.D. 2024-06-29

Občas na člověka přijde potřeba nějak netriviálně transformovat čtyřmístné číslo do jiného čtyřmístného čísla tak, aby to šlo taky zpětně transformovat. Například v PHP programu pracujete s hodnotou, kterou potřebujete posílat přes URL prohlížeče. To číslo, co je vidět v URL, by nemělo být to, co pak používá vlastní program. (Sledujte, jak se mění řádek s adresou této stránky, když odešlete nějaký formulář dole. To jsou právě ta viditelná čísla, ze kterých chcete vytáhnout skrytou, zakódovanou informaci).

Jak na to? Tak především musíte mít chytré známé, kteří vám poradí. Já jsem to zkoušel vymyslet svépomocí a nic kloudného jsem nevymyslel. Samé triviálnosti - funkce a inverzní funkce:

klíč=k=5

kódované_číslo=x=13

zakódované_číslo=y=3*k*(x+k)-2*k

odkódované_číslo=X=(y+2k-3kk)/3k (toto je inverzní funkce k té předchozí)

Hackeři musejí mít hodně velký soubor zakódovaných čísel, aby mohli odhalit funkci, která je kóduje. Takže pokud co chvili měníte kódovací funkci, tak nemají čas ten soubor příkladů vytvořit a odhalení tohoto kodovacího mechanismu je poměrně náročné. Tím spíš, když pravidelně měníte klíč, například pomocí nějakého linearního kongruentního generátoru (linear congruential generator; Low-discrepancy_sequence). Tyto generatory mají jednu výhodu - nahodile prohází pořadí čísel, ale toto pořadí je stabilní a závisí na zvoleném klíči, tzn. kdykoli ho můžete znova obnovit či dokonce zpětně vrátit. Nahodilá pořadí jsou totiž jinak jen jednorázová a nevratná.

function seeded_shuffle(array &$items, $klic) {

$items = array_values($items);

mt_srand($klic);

for ($i = count($items) - 1; $i > 0; $i--) {

$j = mt_rand(0, $i);

list($items[$i], $items[$j]) = array($items[$j], $items[$i]);}

}

function seeded_unshuffle(array &$items, $klic) {

$items = array_values($items);

mt_srand($klic);

$indices = array() ;

for ($i = count($items) - 1; $i > 0; $i--) {

$indices[$i] = mt_rand(0, $i);}

foreach (array_reverse($indices, true) as $i => $j) {

list($items[$i], $items[$j]) = array($items[$j], $items[$i]);}

}

Tyto funkce při klíči 5 z řady 1 až 10 udělají vždy 9, 6, 3, 4, 7, 5, 10, 2, 1, 8, popř. naopak.

jsem tu2

Řada 1-10 zakodovaná pomocí klíče $klic tvoří řadu: "; seeded_shuffle($cisla,$klic); foreach ($cisla as &$i) { echo "$i, ";} echo "

A naopak, tato přeházená řada se pomocí klíče znova obnoví do původního pořádku: "; seeded_unshuffle($cisla,$klic); foreach ($cisla as &$i) { echo "$i, ";} echo "

Jeden matematik-programátor mi ale poradil asi běžně známý algoritmus na kódování čísel pomocí modulárních tříd. S těmi jsem si naposledy hrál, když jsem se zabýval fraktály (Sierpinského koberec). To je už hodně dlouho a stejně jsem to zapomněl, protože je to hodně složité (modulární aritmetika).

To, co mi poradil známý, je podobně geniální jako Sierpinského koberec. Úvaha je prostá: Zakódujeme číslo přes inverzní operaci či prvek v grupě modulárních tříd. Zakódování jde takto:

(Kódované_číslo Operace Klíč) modulus Prvočíslo = Zakodované_číslo

K tomu pak existuje inverzí operace, čili odkódování:

(Zakodované_číslo Operace Inv(Klíč)) modulus Prvočíslo = Odkodované_číslo

To je hodně podobné jako počítání soustavy rovnic s více proměnnými pomocí inverzní matice. U matic je ale výhodou je, že tuto inverzní matici bleskově počítá Calc (Excel) vektorovou algebrou. Logika je tato: Jestliže koeficienty vznikly vynásobením matice s proměnnými, pak proměnné získám tím, že koeficienty vynásobím inverzní maticí. Jednodušší to být nemůže:

Matice*Proměnné=Koeficienty, ergo
Inverzní_matice*Koeficienty=Proměnné, popř.
Matice^-1*Koeficienty=Proměnné Proto i řešení složité soustavy rovnic je s Calcem otázka minuty, než přepíšete hodnoty do tabulky. ^(*)Více zde

Protože to vše je analogické násobení a dělení, tak se inverzní prvek v grupách značí jako index M^-1 a za vším stojí myšlenka "dělení je násobení převrácenou hodnotou čili inverzním prvkem":

2*0,5=1, ergo
2^-1*1=0,5, kde
2^-1 je samozřejmě 1/2.

Celková myšlenka je opravdu takto jednoduchá, a to je právě kouzlo grup. Když je něco grupa, tak na tom matematici mastí tyto operace jako Baťa cvičky.

Grupami jsem se zabýval byť velmi povrchně už na psychologii v rámci vývojové psychologie, když jsem se snažil pochopit koncepty Jeana Piageta, vynikajícího švýcarského vývojového psychologa. Ten s nimi ale pracoval dost volně. Byl jimi okouzlen, protože tou dobou to byla čerstvá matematická novinka.

Teď tedy podrobný návod. Jen poznámka na úvod. Nejsem autorem následujících skriptů, jen jsem je shromáždil z různých stranek, tak abychom je měli hezky pohromadě.

Kde vzít nějaké hezké prvočíslo?

Hezké prvočíslo je to, které je větší než největší číslo, které hodláte použít. Když největšší číslo bude 100, tak kódovací prvočíslo musí být alespoň 101. V praxi samozřejmě můžete používat čísla mnohem větší.

Své hezké prvočíslo si jistě najdete v těchto tabulkách: Sympatické prvočíslo.

Následující funkce je testem, zda určité číslo je či není prvočíslem. Lehce zvládá čísla okolo miliónu (1111967):

function is_prime_fast($n){for($i=~-$n^.5|0;$i&&$n%$i--;);return!$i&$n>2|$n==2;}

Zakódování čísla

$zakodovane_cislo=($kodovane_cislo*$klic)%$prvocislo
Znak procenta % je právě označení pro funkci modulus čili zbytek:
10%8=2 Zbytek, když dělím 10 osmi, je 2.

Inverzní číslo

Inverzní číslo se počítá k ke klíči. Je to takové číslo, jehož součin s klíčem, modulo dané prvočíslo, dává jedna.

(Inverzní_číslo * Klíč) modulus Prvočíslo = 1

To číslo se hledá tak, že prohledáváte všechna čísla menší než dané Prvočíslo, což muže být hodně čísel zvláště, pokud je použité prvočíslo vysoké.

function modInverse($klic, $prvocislo) {

for ($inv_cislo = 1; $inv_cislo < $prvocislo; $inv_cislo++)

if ((($klic%$prvocislo) * ($inv_cislo%$prvocislo)) % $prvocislo == 1)

return $inv_cislo; }

Tato funkce, jak vidíte testuje jedno číslo podruhém, v Calcovském souboru (odkaz na konci stranky) je stejná procedura, jak bych ji učil děti na škole - názorná pro malá čísla. Ale já jsem potřeboval proceduru především pro PHP.

Inverzní číslo pro klíč a prvočíslo je .