Hogy lehet megoldani az a^k = b + c*n egyenletet k-ra és n-re az egész számok halmazán?

Vagyis a (legyorsabban) általános megoldást keresed az a^k ≡ b (mod c) kongruenciára, ahol k az ismeretlen.

Tudjuk hogy az általános esetnek vagy nincs megoldása vagy pontosan egy megoldása van vagy végtelen sok megoldása van.

Az osztási maradékok ciklikusan ismétlődnek. A ciklus c-nél sosem hosszabb, ha d osztója c-nek az esetben meg d-nél semmi képpen sem hosszabb a ciklus hossza.

Ha d osztója c-nek akkor a^k ≡ b (mod c) esetében a^k ≡ b (mod (m/d)) amiből következik hogy a^k ≡ b (mod d)

Ha a kongurencia a*c ≡ b*c (mod m) alakba felírható és c,m számpárok relatív prímek akkor a feladat egyszerűsíthető a ≡ b (mod m) alakba.

Efféléket ki lehet használni már, ha "szerencsénk" van. Azonban általánosságban nem modható el.

Általánosan olyan nehéz probléma, hogy például az RSA titkosítás és a belőle származtatott digitális aláírás így a TLS biztonsági protokoll részben ezen alapszik (mondjuk ezek még meg vannak patkolva, hogy tényleg nehéz legyen).

Ugyanakkor például lineáris kongurencián alapul pszeudo random generátor is.

Vizsgálod a 2^k c-s maradékait abban a reményben, hogy periodicitást fogsz találni. És ott keresed a b 9-es maradékát.

Pl a 2^k 9-es maradékai:

2, 4, 8, 7, 5, 1, 2, ....

jav.: "számpárok relatív prímek"

számpár egymással relatív prím