Pseudorandomness, elliptic curves and sequences of integers  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
72264
Type PD
Principal investigator Gyarmati, Katalin
Title in Hungarian Pszeudovéletlenség, elliptikus görbék és egész számok sorozatai
Title in English Pseudorandomness, elliptic curves and sequences of integers
Keywords in Hungarian pszeudovéletlen, korreláció, eloszlási mérték, elliptikus görbe, sorozat
Keywords in English pseudorandom, correlation, well-distribution measure, elliptic curve, sequence
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Number theory
Panel Mathematics and Computing Science
Department or equivalent Department of Algebra and Number Theory (Eötvös Loránd University)
Starting date 2008-07-01
Closing date 2011-07-31
Funding (in million HUF) 16.380
FTE (full time equivalent) 2.40
state closed project
Summary in Hungarian
A pszeudovéletlen sorozatoknak rengeteg gyakorlati alkalmazása van. Fontos szerepet játszanak a kriptográfiában és a numerikus analízisben. Pályázatom keretében szeretném a pszeudovéletlen sorozatokra vonatkozó kutatásaimat folytatni. Szeretnék minél több, új pszeudovéletlen sorozatot generálni.
C. L. Stewarttal és Sárközy A.-val többdimenziós pszeudovéletlen objektumok, ún. pszeudovéletlen rácsok generálását tervezzük. Pszeudovéletlen rácsok használatosak például a kriptográfiában képek és térképek titkosítása során. Szeretnénk továbbá új pszeudovéletlen mértékeket bevezetni.
C. Mauduittal és Sárközy A.-val többdimenziós pszeudovéletlen mértékek közötti kapcsolatot szeretnénk vizsgálni.
P. Huberttel és Sárközy A.-val fák pszeudovéletlen tulajdonságait tanulmányoznánk.
Rengeteg kriptográfiai rendszer használ elliptikus görbéket. Az OTKA pályázat segítségével lehetőségem nyílna elliptikus görbékkel kapcsolatos kutatásokba is bekapcsolódni. Szeretnék elliptikus görbéket használó pszeudovéletlen generátorokat konstruálni.
Pszeudovéletlen sorozatok és rácsok vizsgálata során gyakran van szükség karakter összegekre. Szeretnék karakterösszeges becsléseket általánosítani és alkalmazni.
Ruzsa Imrével a kombinatorikus számelmélet különböző területein dolgozunk. Eddig három közös cikkünk jelent meg két vagy többtagú összegek közötti összefüggésekről. Szeretném a közös munkát folytatni.
Továbbá szeretném folytatni egész számok sorozatainak valamint véges testek részhalmazainak additív és multiplikatív tulajdonságainak vizsgálatát mind kombinatorikus mind harmonikus analízisbeli eszközökkel.
Úgy érzem, hogy az ELTE Algebra és Számelmélet tanszéke kitűnő helyet biztosítana kutatásaim folytatására. A tanszéken dolgozó kutatókat több mint 10 éve ismerem, PhD disszertációmat is itt írtam, és 6 közös cikkem van a témavezetőmmel. Ezen a tanszéken dolgozik témavezetőm, Sárközy A. is, vele a jövőben is több kutatást tervezek. Önálló kutatásokat is szeretnék folytatni, és ehhez az ELTE minden feltételt biztosít.
Summary
The pseudorandom sequences have many applications in mathematics. They play an important role in cryptography and numerical analysis. In frame of the OTKA scholarship I would like to continue the research of pseudorandomness. I would like to construct new pseudorandom sequences.
Jointly with C. L. Stewart and A. Sárközy we intend to generate more dimensional pseudorandom objects, so called pseudorandom lattices. For example, pseudorandom lattices can be used in cryptography in encryption of digital images and maps. We would like to also introduce new pseudorandom measures in order to study pseudorandom lattices.
With C. Mauduit and A. Sárközy we would like to study the connection between more dimensional pseudorandom measures.
Jointly with P. Hubert and A. Sárközy we will study the pseudorandom properties of trees.
Many cryptosystems use elliptic curves. With the help of the OTKA project I would like to join to the research of elliptic curves. I will construct pseudorandom generators based on elliptic curves. In this research one frequently needs to estimate character sums. I would like to generalize and use such character sums estimates.
With Imre Ruzsa we are working on combinatorial number theory. So far we have published 3 different papers on connections of sums of sets. I would like to continue the joint work.
Furthermore I would like to continue the study of properties of sequences of integers and subsets of finite fields
with combinatorial number theory and harmonic analysis tools.
I think that the Algebra and Number Theory department of ELTE is an excellent place for my research. I have known the professors of the department for more than 10 years, I wrote my PhD dissertation there, and I have 6 joint papers with my thesis advisor. My thesis advisor, A. Sárközy is working at the department and I intend to continue the joint work in the future. I would like to carry on my own researches, and ELTE is a suitable place for this.




 

Final report

  
Results in Hungarian
A projekt időtartama alatt 19 cikket írtam, ezek közül 11 dolgozatom jelent meg, és 4 dolgozatomat fogadtak el már közlésre neves hazai vagy külföldi folyóiratokban. További 4 cikket nyújtottam be közlésre. Az alábbiakban szeretném főbb eredményeimet röviden összefoglalni. Mostanában a pszeudovéletlen sorozatok mellett a többdimenziós pszeudovéletlen objektumok is bekerültek a kutatás főirányvonalába. Kutatásaimat főképp ebben az irányban folytattam, részben egyedül, részben társszerzőkkel. On new measures of pseudorandomness of binary lattices című cikkemben új pszeudovéletlen mértékeket vezettem be pszeudovéletlen rácsok vizsgálatára. On the correlation of subsequences című cikkemben konstruáltam egy sorozatot, melynek a rövid részsorozatai is erős pszeudovéletlen tulajdonságokkal rendelkeznek. Christian Mauduittal és Sárközy Andrással közösen vizsgáltuk az egy és többdimenziós elmélet közötti kapcsolatot. Majd megadtunk több kétdimenziós konstrukciót erős pszeudovéletlen tulajdonságokkal rendelkező rácsokra. Ezeknek a rácsoknak több alkalmazása is van a kriptográfiában, páldául képek, térképek titkosítása során alkalmazzák őket. További dolgozatokban összehasonlítottuk a pszeudovéletlenség különböző mértékeit. Tanulmányoztuk pszeudovéletlen rácsok nagy családjainak a pszeudovéletlen mértékeit. Ruzsa Imrével közösen a négyzetszámok sorozatai között vizsgáltunk 3-tagú számtani sorozat mentes halmazt.
Results in English
During the project I wrote 19 papers, 11 of them have been appeared, other 4 have been accepted for publication in strong leading Hungarian and foreign journals. Further 4 papers have been submitted for publication. Below, I summarize my main results. Recently, besides the pseudorandom sequences, the multi-dimensional pseudorandom-objects are in the center of the research. I continue my research in this direction. I work partly alone and partly with coauthors. In my paper "On pseudorandomness of binary lattices", I introduced new measures of pseudorandomness of binary lattices. In "Correlation of subsequences" I constructed a sequence such that its all subsequences have strong pseudorandom properties. With Christian Mauduit and András Sárközy we studied the connection between the one and multidimensional theory. Later we constructed several constructions of binary lattices with strong pseudorandom properties. These lattices have many applications in cryptography, for example they can be used in encryption of maps and images. In more papers we studied the connection between different pseudorandom measures. We also studied pseudorandom measures of large families of binary lattices. With Imre Ruzsa we gave a large subset of squares which contains no 3-term arithmetic progression.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=72264
Decision
Yes





 

List of publications

  
Katalin Gyarmati, Christian Mauduit, András Sárközy: Measures of pseudorandomness of families of binary lattices, I (Definitions, a constructions using quadratic characters.), Publi. Math. Debrecen, közlésre elfogadva, 2011
Katalin Gyarmati, Christian Mauduit, András Sárközy: Measures of pseudorandomness of families of binary lattices, II (A further construction.), Publi. Math. Debrecen, közlésre elfogadva, 2011
Katalin Gyarmati, András Sárközy, Cameron L. Stewart: On Legendre symbol lattices II, Unif. Distrib. Theory, közlésre leadva, 2011
Katalin Gyarmati: On the correlation of subsequences, Unif. Distrib. Theory, közlésre leadva, 2011
Katalin, Gyarmati, Christian Mauduit: On the correlation of binary sequences, II, Discrete Math., közlésre elfogadva, 2011
Katalin Gyarmati, Imre Ruzsa: A set of squares without arithmetic progression, Acta Arith., közlésre leadva, 2011
Katalin Gyarmati: Concatenation of pseudorandom binary sequences, Periodica Math. Hungar. 58, 99-120, 2009
Katalin Gyarmati: On the complexity of a family related to the Legendre symbol, Periodica Math. Hungar. 58, 209-215, 2009
Katalin Gyarmati: Concatenation of Legendre symbol sequences, Studia Sci. Math. Hungar. 48, 193-204., 2011
Katalin Gyarmati, Pascal Hubert, András Sárközy: Pseudorandom binary functions on almost uniform trees, J. Combin. Number Theory 2, 1-24, 2010
Katalin Gyarmati, Christian Mauduit, András Sárközy: Pseudorandom binary sequences and lattices, Acta Arith. 135, 181-197., 2008
Katalin Gyarmati,: Elliptic curve analogues of a pseudorandom generator, Period. Math. Hungar., közlésre elfogadva, 2010
Katalin Gyarmati, András Sárközy, Cameron L. Stewart: On Legendre symbol lattices, Unif. Distr. Theory 4, 81-95, 2009
Katalin Gyarmati, Christian Mauduit, András Sárközy: Constructions of pseudorandom binary lattices, Unif. Distr. Theory 4, 59-80, 2009
Katalin Gyarmati,: On new measures of pseudorandomness of binary lattices, Acta Math. Hung. 131, 346-359, 2011
Katalin Gyarmati, Christian Mauduit, András Sárközy: Measures of pseudorandomness of finite binary lattices, I (The measures $Q_k$, normality.), Acta Arith. 144, 295-313, 2010
Katalin Gyarmati, Christian Mauduit, András Sárközy: Measures of pseudorandomness of finite binary lattices, II (The symmetry measures.), Ramanujan J. 25, 155-178, 2011
Katalin Gyarmati, Christian Mauduit, András Sárközy: Measures of pseudorandomness of binary lattices, III. ($Q_k$, correlation, normality, minimal values.), Unif. Distrib. Theory. 5, 183-207, 2010
Péter Csikvári, Katalin Gyarmati, András Sárközy,: Density and Ramsey type results on algebraic equations with restricted solution sets, Combinatorica, közlésre benyújtva, 2008



Back »