2^70 mod 561 megoldása? Hogyan jön ki?

2^10 maradéka 463

463^7 maradéka 166

A windows számológépével scientific állásban kiszámolható.

Egy lehetséges megoldás; tudod, hogy 2^10=1024, tehát fel tudod írni azt, hogy

2^70 = (2^10)^7 = 1024 * 1024 * 1024 * 1024 * 1024 * 1024 * 1024

Az 1024-eket tudod maradékosan osztani, majd a maradékoknak veszed a szorzatát:

463 * 463 * 463 * 463 * 463 * 463 * 463

Ezután megteheted azt, hogy kettesével összeszorzod a 463-akat:

214369 * 214369 * 214369 * 463

Újabb maradékos osztás:

67 * 67 * 67 * 463

Ezt pedig már akár egyben is lehet manuálisan szorozni és maradékosan osztani.

Természetesen ennél van gyorsabb megoldás is.

Tehát ezt a kongruenciát akarjuk megoldani:

2^70 = x mod(561)

Az 561 nem prímszám, ezért fel lehet írni prímszámok szorzataként; 561 = 3*11*17

Azt kellene megnéznünk, hogy 3-mal, 11-gyel és 17-tel milyen maradékokat tudunk kapni.

Kezdjük a 3-mal, ezt nem olyan bonyolult manuálisan kiszámolni;

2^1 = 2 3-as maradéka 2

2^2 = 4 3-as maradéka 1

2^3 = 8 3-as maradéka 2

Tehát ha a kitevő páros, akkor a maradék 1. Tehát 2^70 = 1 mod(3).

Ugyanezt meg tudjuk csinálni a 11-gyel is. Ha nem akarunk vele manuálisan vesződni, akkor előhívhatjuk a Kis Fermat-tételt:

[link]

Eszerint 2^10 = 1 mod(11). Mivel 2^70 = (2^10)^7, ezért 2^70-nek is 1 lesz a maradéka, így pedig 2^70 = 1 mod(11)

Végül pedig 17-re:

2^16 = 1 mod(17). Mivel 2^70 = 2^16 * 2^16 * 2^16 * 2^16 * 2^6, ezért így már csak 2^6 17-es maradékát kell megnéznünk, ami azért nem egy bonyolult dolog;

2^6 = 64, ennek a 17-es maradéka 13, tehát 2^70 = 13 mod(17)

Most a következő a feladat: keressük azt a (lehetőleg legkisebb) pozitív egész, x-szel jelölt számot, amelyekre ezek mind igazak, vagyis

x = 1 mod(3)

x = 1 mod(11)

x = 13 mod(17)

Ezt a kongruenciarendszert pedig a kínai maradéktétellel tudjuk megoldani:

[link]

Sajnos a kínai maradéktételben nem vagyok elég járatos. De, ha te ismered, akkor ezzel meg tudod oldani.

> „Gyorshatványozással próbálkoztam, viszont 2^2^6=2^64 is már túl nagy szám,…”

Akkor valamit rosszul csinálsz, mert gyors hatványozással nem szabad, hogy akármelyik lépésben nagyobb számot kapj, mint 561*561… (Ugyanis minden lépést mod 561 csinálsz, így a 0…560 tartományban kaphatsz csak számokat, tehát 560*560 a maximum, ami kijöhet… Néha mondjuk ezen is segíthet, ha eltoljuk a tartományt a 0 köré, de mindegy, ez inkább fejszámolásnál hasznos.)

Gyors hatványozással ugye körülbelül 8 sor kéne legyen, mert 70 < 2^7. Szóval (minden sor mod 561 lesz):

2^0 ≡ 1, //Ezt lehet le se kellene írni, bárminek 1 a 0 hatványa mod bármi (kivéve talán a 0-t, de abba ne menjünk bele).

2^1 ≡ 2 ≡ 1, //Ezután pedig mindig négyzetre emeljük az előző eredményt.

2^2 ≡ 2*2 ≡ 4,

2^4 ≡ 4*4 ≡ 16,

2^8 ≡ 16*16 ≡ 256,

2^16 ≡ 256*256 (= 65536) ≡ 460,

2^32 ≡ 460*460 ≡ 103,

2^64 ≡ 103*103 ≡ 511,//A következő hatvány már több, mint 2^70, így ennyiből már 70 bináris alakja alapján ki tudjuk válogatni a szükséges tényezőket:

2^70 ≡ 2^64 * 2^4 * 2^2 ≡ 511*16*4 ≡ 322*4 ≡ 166.

A hátterét, a gyorshatványozást, a 2-es számrendszerbeli alakot már leírták, matematikailag úgy kijön valóban.

Ha csak simán érdekel az eredmény, és számítógéppel ki akarod számolni, vannak olyan nyelvek, amikbe be van építve a BigInt (tetszőleges hosszúságú egész aritmetika), így nem vagy 64 bitre limitálva. A Python pl. ilyen, ráadásul a moduló hatványozást is alapból támogatja a pow függvénye (a sima ** a hatványozás)

>>> help(pow)

Help on built-in function pow in module builtins:

pow(base, exp, mod=None)

Equivalent to base**exp with 2 arguments or base**exp % mod with 3 arguments

Some types, such as ints, are able to use a more efficient algorithm when

invoked using the three argument form.

>>> pow(2, 70, 561)

166

>>> 2**70

1180591620717411303424

>>> 2**70 % 561

166