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 němelo 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. Ale jeden matematik-programátor mi 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.

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; }

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

Kontrola: (*)% se má rovnat jedné. Tak schválně, čemu se rovná? .

Odkódování čísla

Když máme inverzní číslo k našemu Klíči, pak můžeme snadno odkódovat už jednou zakódované číslo.

$odkodovane_cislo=($zakodovane_cislo*$inverzni_cislo)%$prvocislo

Poznámky

Prostě největší silou zabezpečení mých kol před domem nejsou kamery či elektrický ohradník, ale fakt, že každý zloděj na první pohled vidí, že ta kola jsou neukradnutelná. Odnést je dá víc práce, než co za ně dostane v bazaru.

Samozřejmě chytří zloději mě lehce vykradou, zabijáci snadno zabijí, chytří ajťáci se do mých stránek vlámou s prstem v nose, ale sázím na to, že se to dotyčným moc nevyplácí. Kdo by investoval bůhvíkolik hodin práce špičkového agenta za to, aby zjistil heslo do mých bezvýznamných stránek, které prakticky všechny důležité hodnoty už stejně zobrazují bez hesla.

Neukradnutelnost je velmi sympatická vlastnost, nevyžadující krypotografování, protože je to víceméně přímý derivát toho, co Stopařův průvodce po Galaxii popisuje jako pole Problému někoho jiného (Douglas Adams: Život, vesmír a vůbec):

Nejzvláštnější věcí na lodi bylo sledovat působení pole PNJ. Teď už jasně viděli loď takovou, jaká byla, jednoduše proto, že věděli, že tam je. Bylo však naprosto zřejmé, že nikdo jiný ji neviděl. Nebylo to však proto, že by byla neviditelná a nebylo to ani ničím podobně hypernemožným. Technologické postupy potřebné k tomu, aby se něco stalo neviditelným, jsou totiž tak nekonečně složité, že v devíti stech devadesáti devíti miliardách devíti stech devadesáti devíti mililionech devíti stech devadesáti devíti tisících devíti stech devadesáti devíti případech z bilionu je prostě mnohem jednodušší a efektivnější věc odstranit a obejít se bez ní. Ultraslavný vědecký kouzelník Effrafax z Wugu se jednou vsadil o vlastní život, že za jediný rok učiní velkou megahoru Magramal úplně neviditelnou.

Větší část roční lhůty strávil hraním s mohutnými lux-o-ventily, refrakto-nulátory a se spektrální přesmyčk-o-matikou, a když mu zbývalo už jen pouhých devět hodin, zjistil, že to nedokáže.

A tak se svými přáteli a s přáteli svých přátel a s přáteli přátel svých přátel a s přáteli přátel přátel svých přátel a s některými jejich ne tak úplně dobrými kamarády, kteří náhodou vlastnili mamutí hvězdnou společnost pro kamiónovou dopravu, pustili do toho, co je dnes považováno za nejtvrdší noční makačku v historii. A skutečně, příštího dne nebylo horu Magramal vůbec vidět. Effrafax prohrál sázku - a tudíž i život - jen proto, že jeden pedantský úředník, který měl věc rozsoudit, si všiml, že a) jda místy, kde by měl stát Magramal, o nic nezakopl ani si o nic nerozbil nos, a b) tu byl podezřele vyhlížející měsíc navíc.

Pole Problému Někoho Jiného je mnohem jednodušší a mnohem účinnější, a co víc, může fungovat třeba sto let na energii dodávanou jedinou baterií do obyčejné baterky. Je totiž založeno na přirozeném lidském sklonu nevidět nic, co člověk nechce, neočekává, nebo neumí vysvětlit. Kdyby Effrafax natřel horu na růžovo a na její vrchol umístil laciné, jednoduché pole Problému Někoho Jiného, všichni by určitě chodili kolem ní nebo dokonce přes ni, a prostě by si vůbec nevšimli, že tam je.

Poznámka pod čarou

Pokud občas potřebujete počítat soustavy rovnic, tak vás určitě nadchne tento návod stejně, jako kdysi i mě. Prostě s maticemi a vektory zacházíme přibližně stejně jako s čísly. Dělení je násobení převrácenou hodnotou, čili inverzním prvkem. Tedy 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í. Jak snadné! Bývá to ale hrůza počítat na papíře či s kalkulačkou, proto inverzní matici počítáme v Calcu (Excelu).

Matice*Proměnné=Koeficienty, ergo
Inverzní_matice*Koeficienty=Proměnné, popř.
Matice^-1*Koeficienty=Proměnné

Má-li soustava rovnic tři řádky tvaru: ax + by + cx = k, kde parametry "abc" tvoří čtvercovou matici, "k" jsou tři koeficienty a "xyz" jsou tři proměnné, pak

=MINVERSE(A3:E7) je inverzní matice (A10:E14) k matici abc A3:E7 (pozor zadává se jako maticový vzorec, pomocí ctrl+shift+enter - ne úplně běžná věc, ale fungovalo to kdysi i v Excelu).

=MMULT(A10:E14;F3:F7), kde A10:E14 je inverzní matice a F3:F7 je vektor koeficientů

V jednom adresáři mám pro podobné případy uložených řadu užitečných souborů. Tento například občas používám pro matice, tak si to zkuste napřed v tomto souboru. (Určitě to bude mít hemzy při stahování, ale mělo byt být bez viru, páč je to bez maker.)