hrvatski

Primjena verižnih razlomaka u diofantskim aproksimacijama i kriptoanalizi

U uvodnom dijelu rada dani su osnovni pojmovi o verižnim razlomcima te navedeni osnovni rezultati iz teorije diofantskih aproksimacija. Klasični Legendreov teorem koji kaže da ako je alfa realan broj i a/b racionalan broj koji zadovoljava nejednakost |alfa - a/b| < 1/2b^2 , tada je a/b konvergenta razvoja u verižni razlomak od alfa, generalizirao je Worley na nejednakost |alfa - a/b| < k/q^2 , gdje je k proizvoljan pozitivan realan broj. Opisao je rješenja dane nejednakosti u obliku (a, b) = (rp_{;m+1}; +- sp_{;m};, rq_{;m+1}; +- sq_{;};m), gdje su r i s nenegativni cijeli brojevi koji zadovoljavaju uvjet rs < 2k. U radu je Worleyev rezultat proširen i dane su eksplicitne verzije za k = 3, 4, ... , 13, te je dana lista parova relativno prostih brojeva (r, s) koji se pojavljuju u zapisu rješenja dane nejednakosti, i na primjerima je pokazano da niti jedan od tih parova ne može biti izostavljen. Pokazano je da se uvjet rs < 2k ne može zamijeniti uvjetom rs < (2 - epsilon)k, za neki epsilon > 0. U radu je u potpunosti riješena jednoparametarska familija Thueovih nejednadžbi |x^4 - 2cx^3y + 2x^2y^2 + 2cxy^3 + y^4| <= 6c + 4. Tzanakisovom metodom smo problem sveli na rješavanje sustava od dvije pellovske jednadžbe sa zajedničkom nepoznanicom. Koristeći dobivene rezultate smo za obje pellovske jednadžbe sustava odredili one m za koje je |m| <= 6c+4 i za koje jednažbe imaju rješenja te dobili da jednadžba x^4 - 2cx^3y + 2x^2y^2 + 2cxy^3 + y^4 = m ima rješenja ako je m = 1 ili 4, te u slučajevima c = 3 i 4 i ako je m = -12c + 25. Za dobivanje donje granice za rješenje tog sustava koristili smo metodu kongruencija koju su uveli Dujella i Petho, a za dobivanje gornje granice koristili smo Baker-Wustholzov i Bennettov teorem. U radu je takoder prikazana primjena verižnih razlomaka u kriptoanalizi. Izvršili smo kriptoanalizu LUC i KMOV kriptosustava pomoću varijante Wienerovog napada koju je opisao Dujella. Opisali smo algoritam za nalaženje tajnog eksponenta d u obliku d = rq_{;m+1}; +- sq_{;m};, za nenegativne cijele brojeve r i s. Pinch je 1995. godine proširio poznati Wienerov napad na LUC i KMOV kriptosustave. Pokazao je da su oni nesigurni, uz 1024-bitni modul n, za 256-bitni tajni eksponent d. U radu je pokazano da su LUC i KMOV kriptosustavi, uz iste pretpostavke na n, nesigurni za 270-bitni tajni eksponent d.

verižni razlomci; Thueove jednadžbe; kriptoanaliza

nije evidentirano