Computational number theory and its applications in cryptography  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
38225
Type K
Principal investigator Pethő, Attila
Title in Hungarian Algoritmikus számelmélet és alkalmazásai a kriptográfiában
Title in English Computational number theory and its applications in cryptography
Panel Mathematics and Computing Science
Department or equivalent Department of Computer Science (University of Debrecen)
Participants Bérczes, Attila
Győry, Kálmán
Herendi, Tamás
Horváth, Géza
Starting date 2002-01-01
Closing date 2005-12-31
Funding (in million HUF) 9.628
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
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.
Results in English
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.
Full text http://real.mtak.hu/513/
Decision
Yes





 

List of publications

  
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



Back »