Algoritmikus számelmélet és alkalmazásai a kriptográfiában = Computational number theory and its applications in cryptography

Pethő, Attila and Bérczes, Attila and Győry, Kálmán and Herendi, Tamás and Horváth, Géza (2006) Algoritmikus számelmélet és alkalmazásai a kriptográfiában = Computational number theory and its applications in cryptography. Project Report. OTKA.

Preview

PDF 38225_ZJ1.pdf Download (141kB)

Abstract

Megmutattuk, hogy a normaforma függvényt moduló pq redukálva, ahol p és q nagy prímszámok, ütközésmentes függvényt kapunk. Több konstrukciót elemeztünk kriptográfiai alkalmazások szempontjából releváns véletlen sorozatcsaládra. Ha Gn(x) egy algebrailag zárt test feletti lineáris rekurzív polinomsorozat és x,y algebrailag függőek, akkor bebizonyítottuk, hogy a Gn(x)=Gm(y) egyenletnek általános feltételek mellett csak véges sok megoldása van n,m-ben. Bebizonyítottuk, hogy egy normaforma egyenletnek általában csak véges sok olyan megoldása van, ahol a megoldások koordinátái egy számtani sorozatot alkotnak. Megadtuk a klasszikus ?-reprezentáció és a kanonikus számrendszerek egy közös általánosítását és több dolgozatban vizsgáltuk ezen SRS-nek elnevezett fogalom tulajdonságait. Elemzésünk választ ad arra, hogy miért nehéz a harmadfokú CNS polinomok, illetve az (F) tulajdonságú Pisot számok jellemzése. Megfogalmaztuk a következő sejtést: Legyen |?|<2 és {an} egész számok olyan sorozata, amelyre 0 ? an-1+ ? an + an+1 <1 minden n-re. Akkor {an} periódikus. Számos korábbi eredményt messzemenően általánosítva, mély eredményeket értünk el két klasszikus, Fermat-ig és Eulerig visszanyúló diofantikus témakörben, nevezetesen számtani sorozatokban, illetve hatványösszegekben található teljes hatványokra vonatkozóan. Többek között megmutattuk, hogy egészekből álló k-tagú számtani sorozat tagjainak szorzata k ? 11-re általában nem lehet teljes hatvány. | Considering the reduction modulo pq, where p and q are big primes we constructed collision resistant hash functions. We studied some construction of cryptography relevant pseudo random number sequences. If Gn(x) denotes a linear recursive polynomial sequence over an algebraically closed field and x,y are algebraically dependent, then we proved that the equation Gn(x)=Gm(y) has under quite general assumptions only finitely many solutions in n,m. We proved that a norm form equation has only finitely many solutions, which coordinates form an arithmetical progression. We realized a common generalization, called shift radix system, of the classical ?-reprezentation and the canonical number systems and studied its properties in several papers. Our investigation showed that the characterization problem of cubic CNS polynomials and Pisot numbers of proprty (F) is complicated. We made rise the conjecture: Let |?|<2 and {an} a sequence of integers staisfying the inequality 0 ? an-1+ ? an + an+1 <1 for all n. Then {an} is periodical. Generalyzing essentially several earlier results, we achieved deep results in two classical diophantine topics: perfect powers in arithmetical progressions and in power sums, which are going back to Farmat and Euler. We proved among others that the product of members of an arithmetical progression of length at most 11 apart from trivial cases cannot be a perfect power.

Actions (login required)

Edit Item