Metoda opakování čtverců je algoritmus urychlující umocňování celých čísel v nějakém okruhu modulo n. Je založen na rozkladu mocnitele na mocniny dvojky.

Postup při výpočtu

Výpočet se provádí následujícím postupem:

  1. Exponent se převede do binární soustavy.
  2. Z tohoto binárního zápisu se vytvoří tzv. řídící řetězec složený ze znaků S (square) a X (times).
  3. Na základě řídícího řetězce se provede výpočet, který se dá přirovnat ke spuštění programu na střadačovém procesoru.

Tvorba řídícího řetězce

Řídící řetězec lze připodobnit k programu jednoduchého střadačového procesoru s celočíselným střadačem W. Na počátku je ve střadači hodnota 1. Procesor má dvě instrukce S (square) a X (times), které mají následující sémantiku:

InstrukceSémantikaPopis
SW = (W * W) % Ndo střadače ulož druhou mocninu střadače modulo N
XW = (W * A) % Ndo střadače ulož násobek střadače a základu A, to celé modulo N

Řídící řetězec se vytváří na základě binárního zápisu exponentu. Ten se čte po znacích zleva doprava a řídící řetězec vzniká postupně dle následujících pravidel:

  • 0 se přeloží na S
  • 1 se přeloží na XS
  • poslední znak řídícího řetězce (vždy S) se odebere

Několik příkladů exponentů a jejich řídících řetězců:

ExponentBinární zápisŘídící řetězec
11X
210XS
5101XSSX
151111XSXSXSX
2811100XSXSXSS
44101100XSSXSXSS
721001000XSSSXSSS
891011001XSSXSXSSSX
15310011001XSSSXSXSSSX

Také je možné jednotlivé číslice binárního zápisu proložit znaky S a na pozice, kde je 1, zapsat X. Oba uvedené způsoby jsou ekvivalentní.

ČísloBinárněVložení znaku SVložení znaku XVýsledek
51011S0S1XS0SXXSSX
441011001S0S1S1S0S0XS0SXSXS0S0XSSXSXSS
8910110011S0S1S1S0S0S1XS0SXSXS0S0SXXSSXSXSSSX

Příklady

Zadání

Umocněte 17 na 51 v okruhu modulo 312.

£ 17^{51} \;\;\mathrm{v}\; \mathbb{Z}_{312} £

Řešení

Nejprve převedeme číslo 51 do binární soustavy. Výsledkem je číslo 110011, ze kterého vytvoříme řídící řetězec XSXSSSXSX. Znaky řídícího řetězce napíšeme pod sebe a zahájíme výpočet.

InstrukceVýznamVýsledek (akumulátor)
-inicializace1
Xvynásob 1717
Sumocni17 * 17 = 289
Xvynásob 17289 * 17 = 4913 = 233
Sumocni233 * 233 = 1
Sumocni1 * 1 = 1
Sumocni1 * 1 = 1
Xvynásob 171 * 17 = 17
Sumocni17 * 17 = 289
Xvynásob 17289 * 17 = 4913 = 233

Výsledek je tedy:

£ 17^{51} = 233 \;\;\mathrm{v}\; \mathbb{Z}_{312} £

Zadání

Umocněte 571 na 2691 v okruhu modulo 1469.

£ 571^{2691} \;\;\mathrm{v}\; \mathbb{Z}_{1469} £

Řešení

Nejprve převedeme číslo 2691 do binární soustavy. Výsledkem je číslo 100001101, ze kterého vytvoříme řídící řetězec XSSSSSXSXSSX. Znaky řídícího řetězce napíšeme pod sebe a zahájíme výpočet.

InstrukceVýznamVýsledek (akumulátor)
-inicializace1
Xvynásob 571571
Sumocni571 * 571 = 326041 = 1392
Sumocni1392 * 1392 = 1937664 = 53
Sumocni53 * 53 = 1340
Sumocni1340 * 1340 = 1795600 = 482
Sumocni482 * 482 = 232324 = 222
Xvynásob 571222 * 571 = 126762 = 428
Sumocni428 * 428 = 183184 = 1028
Xvynásob 5711028 * 571 = 586988 = 857
Sumocni857 * 857 = 734449 = 1418
Sumocni1418 * 1418 = 2010724 = 1132
Xvynásob 5711132 * 571 = 646372 = 12

Výsledek je tedy:

£ 571^{2691} = 12 \;\;\mathrm{v}\; \mathbb{Z}_{1469} £

Princip

£ a^{11} = a^{2^3 + 2^1 + 2^0} = ((a^2)^2 \cdot a)^2 \cdot a \rightarrow \mathrm{XSSXSX} £

Reference

  • předmět X01AVT na FEL ČVUT