Cvičení č. 1: Modulární aritmetika

Tomáš Kalvoda, KAM FIT ČVUT, 2016-2019

Úvod

Začněme nejprve odpovědí na otázku, co je to modulo?

Jistě znáte zbytek po dělení: je-li $a\in\mathbb{Z}$ a $p\in\mathbb{N}$, potom existují čísla $q\in\mathbb{Z}$ a $r\in\mathbb{Z}$ splňující $0 \leq r < p$ a $a = q\cdot p + r$. O $r$ mluvíme jako jako o zbytku po dělení čísla $a$ číslem $p$. Značíme $r = a \bmod p$.

Je-li $p\in\mathbb{N}$ zvoleno pevně, pak zjevně $r \in \mathbb{Z}_p := \{0,1,\ldots,p-1\}$, ať už hodnota $a$ byla jakákoliv (celočíselná).

To nás motivuje k následujícím definicím. Definujeme operace $+$ a $\cdot$ na množině $\mathbb{Z}_p$ následujícím způsobem: $a + b := (a+b) \bmod p \quad \text{a} \quad a \cdot b := (a \cdot b) \bmod p,$ kde $+$ a $\cdot$ na pravé straně jsou obyčené sčítání a násobení v $\mathbb{Z}$ a na jejich výsledku se poté vypočte zbytek po dělení číslem $p$.

Lze ukázat, že takto zavedené operace na $\mathbb{Z}_p$:

• jsou každá komutativní a asociativní,
• násobení je distributivní vůčí sčítání,
• číslo $0$ je neutrálním prvkem vůči sčítání, ke každému $a\in\mathbb{Z}_p$ je $-a := p - a$ prvek opačný k $a$,
• číslo $1$ je neutrální prvek vůči násobení,
• s inverzními prvky vůči násobení je situace složitější, v tento okamžik si pouze řekněme, že existují za předpokladu prvočíselnosti $p$. Ke každému nenulovému $a$ pak existuje $a^{-1}$ splňující $a \cdot a^{-1} \bmod p = 1$. Explicitní předpis pro ně ovšem neexistuje, ale lze je hledat pomocí rozšířeného Euklidova algoritmu.

Jinak řečeno, je-li $p\in\mathbb{N}$ prvočíslo, pak $Z_p$ s operacemi sčítání a násobení modulo $p$ tvoří těleso.

Chceme-li v SageMath počítat operaci modulo můžeme k tomu použít funkci mod.

mod(5, 4)

1

mod(13, 5)

3

13 % 5 # alternativní infixová notace

3

Toto ale není nejlepší a nejvhodnější způsob jak nad výše popsanou strukturou uvažovat. Funkce mod pracuje s integery.

Níže si ukážeme, jak je modulární aritmetika implementovaná v SageMath pomocí OOP (objektově orientovaného programování) a jak tento přístup pěkně kopíruje abstraktní koncept tělesa.

OOP pohled na modulární aritmetiku

SageMath umožňuje pracovat s tělesem samotným (s množinou na které jsou definovány algebraické operace sčítání a násobení se známými vlastnostmi). Vytvořme těleso $\mathbb{Z}_p$ pro volbu $p = 13$.

T = IntegerModRing(order=13) # ekvivalentně T = GF(13), Galois Field
T

Ring of integers modulo 13

SageMath ví, že se jedná o těleso:

T.is_field()

True

Zná počet jeho prvků:

T.order()

13

Prvky tohoto tělesa jsou opravdu takové jak čekáme.

list(T)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Další metody na objektu $T$ mohou být také užitečné, například můžeme snadno sestavit tabulku sčítání a násobení.

T.addition_table('digits')

 +  00 01 02 03 04 05 06 07 08 09 10 11 12
  +---------------------------------------
00| 00 01 02 03 04 05 06 07 08 09 10 11 12
01| 01 02 03 04 05 06 07 08 09 10 11 12 00
02| 02 03 04 05 06 07 08 09 10 11 12 00 01
03| 03 04 05 06 07 08 09 10 11 12 00 01 02
04| 04 05 06 07 08 09 10 11 12 00 01 02 03
05| 05 06 07 08 09 10 11 12 00 01 02 03 04
06| 06 07 08 09 10 11 12 00 01 02 03 04 05
07| 07 08 09 10 11 12 00 01 02 03 04 05 06
08| 08 09 10 11 12 00 01 02 03 04 05 06 07
09| 09 10 11 12 00 01 02 03 04 05 06 07 08
10| 10 11 12 00 01 02 03 04 05 06 07 08 09
11| 11 12 00 01 02 03 04 05 06 07 08 09 10
12| 12 00 01 02 03 04 05 06 07 08 09 10 11

T.multiplication_table('digits')

 *  00 01 02 03 04 05 06 07 08 09 10 11 12
  +---------------------------------------
00| 00 00 00 00 00 00 00 00 00 00 00 00 00
01| 00 01 02 03 04 05 06 07 08 09 10 11 12
02| 00 02 04 06 08 10 12 01 03 05 07 09 11
03| 00 03 06 09 12 02 05 08 11 01 04 07 10
04| 00 04 08 12 03 07 11 02 06 10 01 05 09
05| 00 05 10 02 07 12 04 09 01 06 11 03 08
06| 00 06 12 05 11 04 10 03 09 02 08 01 07
07| 00 07 01 08 02 09 03 10 04 11 05 12 06
08| 00 08 03 11 06 01 09 04 12 07 02 10 05
09| 00 09 05 01 10 06 02 11 07 03 12 08 04
10| 00 10 07 04 01 11 08 05 02 12 09 06 03
11| 00 11 09 07 05 03 01 12 10 08 06 04 02
12| 00 12 11 10 09 08 07 06 05 04 03 02 01

Prvky tohoto tělesa vytváříme v nejjednodušším případě tak, že SageMath požádáme o vnoření celého čísla do tohoto tělesa:

T(20)

7

T(4)

4

T(4) in T

True

type(T(4))

<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>

Pomocí metody parent můžeme zjistit, jak nad daným objektem Sage "uvažuje".

print(T(20).parent())
print(20.parent())

Ring of integers modulo 13
Integer Ring

S prvky tělesa můžeme snadno pracovat pomocí obyčejných operátorů + a *:

a = T(7); b = T(9);
print(a + b)
print(a * b)

3
11

Můžeme SageMath požádat o opačný prvek (vůči sčítání):

for c in T:
    print("c = %s, -c = %s" % (c, -c))

c = 0, -c = 0
c = 1, -c = 12
c = 2, -c = 11
c = 3, -c = 10
c = 4, -c = 9
c = 5, -c = 8
c = 6, -c = 7
c = 7, -c = 6
c = 8, -c = 5
c = 9, -c = 4
c = 10, -c = 3
c = 11, -c = 2
c = 12, -c = 1

Vidíme přesně to co jsme už předestřeli v úvodníku. Řád je jasný. Jak je to ovšem s násobením? K výpočtu multiplikativní inverze můžeme využít notaci používanou i v definici inverzí.

ainv = a^(-1) # multiplikativní inverze k 7 v modulu 13
print(ainv)

2

Ano, toto je správná odpověď. Otestujme toto tvrzení z definice:

print(a * ainv)
print(ainv * a)

1
1

A podívejme se ještě na tabulku multiplikativních inverzí (pro prvky různé od nulového prvku).

for c in T:
    if not c.is_zero():
        print("a = %s, a^(-1) = %s" % (c, c^(-1)))

a = 1, a^(-1) = 1
a = 2, a^(-1) = 7
a = 3, a^(-1) = 9
a = 4, a^(-1) = 10
a = 5, a^(-1) = 8
a = 6, a^(-1) = 11
a = 7, a^(-1) = 2
a = 8, a^(-1) = 5
a = 9, a^(-1) = 3
a = 10, a^(-1) = 4
a = 11, a^(-1) = 6
a = 12, a^(-1) = 12

Porovnejte s podobným výpisem pro opačné prvky (aditivní inverze). Nyní vůbec není jasné, který prvek má kterou inverzi. Tohoto faktu se s úspěchem využívá v kryptologii.

Řešený příklad z cvičení (1.8)

Ukažme si, jak v SageMath vyřešit jeden příklad na výpočet řešení soustavy v modulární aritmetice. V SageMath je postup velmi jednoduchý, rozbor detailů ale odsuneme na pozdější dobu, až budeme mít vytvořený potřebný teoretický aparát.

T = IntegerModRing(2)
T.is_field()

True

Matice a vektory s prvky z tělesa $T$.

A = matrix(T,[
        [1,0,1,0,0],
        [1,1,0,1,1],
        [0,0,1,1,0],
        [0,1,0,1,0],
        [0,1,0,0,1]
    ])
b = vector(T,[1,1,1,1,1])

Pěkné zobrazení matice.

show(A)

type(A)

<class 'sage.matrix.matrix_mod2_dense.Matrix_mod2_dense'>

A vektoru.

show(b)

Najdi partikulární řešení soustavy s maticí soustavy $A$ a pravou stranou $b$.

A.solve_right(b)

(0, 1, 1, 0, 0)

Najdi jádro matice $A$.

A.right_kernel()

Vector space of degree 5 and dimension 1 over Ring of integers modulo 2
Basis matrix:
[1 1 1 1 1]

Vzhledem k tomu, že v tělese máme jenom $0$ a $1$ jsou všechna řešení dvě, přesně $(0,1,1,0,0)$ a $(0,1,1,0,0) + (1,1,1,1,1) = (1,0,0,1,1)$.

Poznámka: $p$ musí být prvočíslo

Člověka přirozeně napadne, proč $p$ musí být prvočíslo, proč by se nemohlo počítat modulo nějaké libovolné pevně zvolené celé číslo $n \in \mathbb{N}$. Odpověď je jednoduchá, pokud by modulo ($n$) nebylo prvočíslo, pak by výsledná struktura nebyla těleso. Některé prvky v něm (všechna čísla soudělná s $n$) by neměla inverzi. Ukažme to na příkladě počítání modulo $n=12$.

R = IntegerModRing(12)
R

Ring of integers modulo 12

Tvrdíme, že například $x = 4$ nemá svou inverzi v této množině, tj. pro každé $y$ z této množiny platí, že $x \cdot y \neq 1$:

x = R(4)
for y in R:
    print(x * y)

0
4
8
0
4
8
0
4
8
0
4
8

Vidíte, ani jedna jednička. Čtyřkou proto v této aritmetice nelze dělit. Množina $\{0,1,\ldots,11\}$ s počítáním modulo $12$ netvoří těleso.

I Sage o tom ví:

R.is_field()

False