Algoritmikus számelmélet és alkalmazásai a kriptográfiában  részletek

súgó  nyomtatás 
vissza »
 

Projekt adatai

  
azonosító
38225
típus K
Vezető kutató Pethő Attila
magyar cím Algoritmikus számelmélet és alkalmazásai a kriptográfiában
Angol cím Computational number theory and its applications in cryptography
zsűri Matematika–Számítástudomány
Kutatóhely IK Számítógéptudományi Tanszék (Debreceni Egyetem)
résztvevők Bérczes Attila
Győry Kálmán
Herendi Tamás
Horváth Géza
projekt kezdete 2002-01-01
projekt vége 2005-12-31
aktuális összeg (MFt) 9.628
FTE (kutatóév egyenérték) 0.00
állapot lezárult projekt





 

Zárójelentés

  
kutatási eredmények (magyarul)
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.
kutatási eredmények (angolul)
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.
a zárójelentés teljes szövege http://real.mtak.hu/513/
döntés eredménye
igen





 

Közleményjegyzék

  
K. Győry A. Pintér: Almost perfect powers in products of consecutive integers, Monatsh. Math.145 (2005), 19-33, 2005
Cl. Fuchs, A. Pethő, R.F. Tichy: On the diophantine equation $G_{n}(x)=G_{m}(y)$ with $Q(x,y)=0$, közlésre benyújtva, 2004
Cl. Fuchs, A. Pethő: Effective bounds for the zeros of linear recurrences in function fields, J. Theorie Nombres de Bordeaux, megjelenés alatt, 2006
A. Bérczes, A. Pethő: On norm form equations with solutions forming arithmetic progressions, Publ. Math. Debrecen, 65 (2004), 281-290., 2004
K. Gyarmati, A. Sárközy, A. Pethő: On linear recursion and pseudorandomness, Acta Arith., 118 (2005), 359 - 374., 2005
S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, J. Thuswaldner: Generalized radix representations and dynamical systems I, Acta Math. Acad. Sci. Hungar, 108 (2005), 207 - 238., 2005
S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, J. Thuswaldner: On a generalization of the radix representation - a survey, Fields Institute Communications, 41, 2004, 19-27., 2004
A. Pethő: Connections between power integral bases and radix representations in algebraic number fields, Proc. 2003 Nagoya Conf. Yokoi-Chowla Conj. and Related Problems\'', Eds.: S-i. Katayama, C. Levesque and T. Nakahara, Furukawa Total Pr. 2004, 115-125., 2004
G. Barat, Ch. Frougny, A. Pethő: On linear recurrent Mahler numbers, Integers, {\bf 5} (2005) \#A1, 17 pp. http://www.westga.edu/~integers/vol5-3.html, 2005
T. Herendi: Uniform distribution of linear recurring sequences modulo prime powers, Finite Fields and Their Applications 10 (2004) 1-23, 2004
K. Győry, L. Hajdu, N. Saradha: On the diophantine equation $n(n+d)...(n+(k-1)d) = by^l$, Canad. Math. Bull.47 (2004),373-388., 2004
K. Győry , A. Pintér: On the equation $1^ k+2^k+�+ x^k=y^n$, Publ. Math Debrecen 62(2003)403-414, 2003
K. Győry: On some aritmetical properties of Lucas and Lehmer numbers II, Acta Acad. Paed. Agriensis, Sect Math. 30(2003),67-73, 2003
M. Benett, K. Győry, A. Pintér: On the Diophantine equation $1^k+2^k+…+x^k=y^n$, Compositio Math.140(2004) 1417-31., 2004
K. Győry: Perfect powers in products with consecutive terms from aritmetic progressions, megjelenés alatt, 2004
K. Győry, L. Hajdu, A. Pintér, A. Schinzel: Polynomials determined by a few of their coefficients, Indag. Math.15(2004) 209-21., 2004
A. Bérczes, J.H. Evertse, K. Győry: On the number of equivalence classes of binary forms of given degree and given discriminant, Acta Arith.113(2004) 363-99., 2004
Y. Bugeaud, K. Győry: On binominal Thue-Mahler equations, Periodica Math. Hungarica 49(2004),25-34., 2004
G. Everest, K. Győry: On some aritmetical properties of solutions of decomposable form equations, Math. Proc. Cambridge Philos. Soc., megjelenés alatt, 2004
M. Bennett, K. Győry, L. Hajdu: Powers from products of consecutive terms in aritmetic progression, Proc. London Math. Soc.. megjelenés alatt, 2004
Y. Bilu, I. Gaál, K. Győry: Index form equations in sextic fields: a hard computation, Acta Arith115(2004) 85-96., 2004
K. Győry, A. Pintér: Almost perfect powers in products of consecutive integers, megjelenés alatt, 2004
K. Győry, A. Pethő and Á. Pintér: Béla Bridza (1958-2003), Publ. Math. Debrecen 65 (2004), 1-11., 2004
K. Győry,: Index form equations and their applications,, The Proc. of the Institute of Math. of NAN of Belarus, 13 (2005), megjelenés alatt, 2005
K. Győry, I. Pink and Á. Pintér: Power values of polynomials and binomial Thue-Mahler equations., Publ. Math. Debrecen 65 (2004), 341-362., 2004
K. Győry,: Polinomials and binary forms with given discriminant,, megjelenés alatt, 2004
M. Bennett, K. Győry, M. Mignotte, Á. Pintér: Binomial Thue equatipons and polynomial powers,, megjelenés alatt, 2004
G. Horváth: A $\varphi$ faktorizáló algoritmus, Alkalmazott Matematikai Lapok 21, (2004), 253-262., 2004
S. Akiyama, H. Brunotte, A. Pethő: Cubic CNS polynomials, notes on a conjecture of W.J. Gilbert, J. Math. Anal. and Appl., 281 (2003), 402--415., 2003
S. Akiyama, H. Brunotte, A. Pethő, J. Thuswaldner: Generalized radix representations and dynamical systems II, Acta Arith. 121 (2006), 21-61., 2006
S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, J. Thuswaldner: Basic properties of shift radix systems, Acta Math. Acad. Paed. Nyíregyháziensis, megjelenés alatt, 2006
S. Akiyama, A. Pethő: On canonical number systems, Theor. Comp. Sci., 270 (2002), 921--933., 2002
S. Akiyama, H. Brunotte, A. Pethő, W. Steiner: Remarks on a conjecture on certain integer sequences, Periodica Mathematica Hungarica, megjelenés alatt, 2006
A. Bérczes, A. Pethő and V. Ziegler: Parameterized Norm Form Equations with Arithmetic Progressions, J. Th\'eorie Nombres de Bordeaux, to appear., 2006
H. Brunotte, A. Huszti, A. Pethő: Bases of canonical number systems in quartic algebraic number fields, J. Th\'eorie Nombres de Bordeaux, submitted, 2006
Cl. Fuchs, A. Pethő, R.F. Tichy: On the diophantine equation $G_n(x) = G_m(P(x))$, Monatshefte Math., 137 (2002), 173--196., 2002
Cl. Fuchs, A. Pethő, R.F. Tichy: On the Diophantine equation $G_n(x)=G_m(P(x))$: higher order recurrences, Trans. Amer. Math. Soc., 355 (2003), 4657--4681., 2003
E. Herrmann, I. Járási, A. Pethő: Note on J.H.E. Cohn's paper "The Diophantine equation $x^n=Dy^2+1$", Acta Arith., 113 (2004), 69--76., 2004
C. Heuberger, A. Pethő, R.F. Tichy: Thomas' family of Thue equations over imaginary quadratic fields, J. Symbolic Comp., 34 (2002), 437-449., 2002
V. Komornik, P. Loretti, A. Pethő: The smallest univoque number is not isolated, Publ. Math. Debrecen, 62/3-4 (2003), 429--435., 2003
A. Pethő: Notes on $CNS$ polynomials and integral interpolation, megjelenés alatt, 2003
Pethő Attila: Egy negyedrendű rekurzív sorozatcsaládról, Acta Acad. Paed. Agriensis Sect. Math., 30 (2003), 115-122., 2003
S. Schmitt and H.G. Zimmer: Elliptic Curves - A Computational Approach, with an Appendix by Attila Pethő, de Gruyter Studies in Mathematics: 31, 2003., 2003
A. Bérczes, A. Pethő: Computational experiences on norm form equations with solutions forming arithmetic progressions, Glasnik Math., to appear, 2006
A. Bérczes, K. Győry: On the number of solutions of decomposable polynomial equations, Acta. Arith., 101(2002) 171-187., 2002
G. Everest, I. Gaál, K.Győry, G. Röttger: On the spatial distribution of solutions of decomposable form equations, Math. Comp., 71(2002), 633-648., 2002
K. Győry: On the number of primitive solutions of Thue equations and Thue inequalities, Paul Erdős and His Mathematics, 2002, 279-294., 2002
K. Győry: Solving diophantine equations by Baker’s theory, A Panorama of Number Theory, 2002, 38-72., 2002
A. Bérczes, J. Ködmön: Methods for the calculation of values of a norm form, Publ. Math. Debrecen, 2003, 751-768, 2003
G. Everest, K. Győry: On some aritmetical properties of solutions of decomposable form equations, Math. Proc. Cambridge Philos. Soc.139(2005), 27-40, 2005
A. Bérczes, J. Ködmön, A. Pethő: A one-way function based on norm form equations, Periodica Math. Hung. 49, 1-13, 2004, 2004
K. Győry, K. Yu: Bounds for the solutions of S-unit equations and decomposable form equations, Acta Arith.,2005, 2005
M. Bennett, K.Győry, A. Pintér: On the Diophantine equation 1k+2k+…+xk=yn, Compositio Math. 140, 1417-1431., (2004), 2004
A. Bérczes, J.H. Evertse, K.Győry: Diophantine problems related to discriminants and resultants of binary forms, Diophantine Geometry, 2007
N. Bruin, K. Győry, L. Hajdu and Sz. Tengely: Arithmetic progressions consisting of unlike powers, Indag Math, megjelenés alatt, 2005, 2005



vissza »