Abstract | Keywords | Export | Availability | Bookmark

Choose an application

• Reference Manager
• EndNote
• RefWorks (Direct export to RefWorks)

Het is intussen reeds enkele decennia geleden dat Koblitz en Miller voorstelden om elliptische krommen of de jacobianen van hyperelliptische krommen over eindige velden te gebruiken als geschikte groepen voor een cryptografisch discrete-logaritme probleem (DLP). Opdat dit DLP voldoende veiligheid zou garanderen, is het heel belangrijk de orde van de groep te kennen, deze moet bijvoorbeeld deelbaar zijn door een grote priemfactor. In deze thesis ontwikkelen we een p-adische cohomologie die toelaat algoritmes te ontwerpen om de orde van zulke groepen efficiënt te bepalen. In 2001 gebruikte Kedlaya de reeds veel oudere cohomologie van Monsky en Washnitzer in een algoritme dat de zeta functie van een hyperelliptische kromme van genus g berekent. Deze cohomologie is een 2g-dimensionale p-adische vectorruimte waarop een Frobenius-operator werkt, waarbij de karakteristieke veelterm van deze operator de zeta-functie geeft. Enkele jaren later vormde Lauder werk van Dwork om tot een algoritme om de zeta-functie van hyperoppervlakken te bepalen. Centraal hierbij is het concept deformatie: het inbedden van het hyperoppervlak in een familie met (minstens) één makkelijke variëteit in de familie. De verandering van de Frobenius operator doorheen de familie wordt dan vastgelegd door een p-adische differentiaalvergelijking. Mijn werk combineert deze twee ideeën en bestaat erin een relatieve Monsky-Washnitzer cohomologie te construeren (i.e. niet voor één kromme zoals Kedlaya, maar voor de ganse familie) voor hyperelliptische krommen en het zoeken van een vorm van de differentiaalvergelijking die geschikt is voor algoritmische doeleinden. Voor welgekozen families E(G), waarbij E(0) over een heel klein eindig veld gedefinieerd is, kunnen we de differentiaalvergelijking oplossen op zeer efficiënte wijze. Dit geeft aanleiding tot een algoritme dat voor krommen in zulke families de zeta-functie bepaalt met veel minder geheugenruimte dan Kedlaya's algoritme. Daarenboven kan het algoritme ook asymptotisch (en in praktijk) sneller gemaakt worden. Een implementatie in oneven karakteristiek geeft uitermate interessante resultaten. Door de strategie die we gebruiken voor het oplossen van de differentiaalvergelijking aan te passen en een ander type familie te kiezen, hebben we ook een algoritme ontwikkeld dat voor elke hyperelliptische kromme werkt en dat nog steeds veel minder geheugen vraagt dan het algoritme van Kedlaya. In een laatste resultaat geven we een specifiek algoritme voor elliptische krommen dat kwadratisch werkt in de uitbreidingsgraad van het eindig veld. Dit is mogelijk doordat de Frobenius-operator 'semi-gediagonaliseerd' kan worden. De orde van een elliptische kromme over een eindig veld van graad 100 en karakteristiek 3 kan hiermee berekend worden in een halve seconde. The use in cryptography of the group structure on elliptic curves or the jacobians of hyperelliptic curves over finite fields has been suggested already a few decades ago. In order to exploit the difficulty of the discrete logarithm problem on these groups, their size is a parameter of central importance. In this thesis we develop a certain p-adic analytic cohomology theory which gives rise to algorithms that can compute those sizes in a very efficient way. In 2001 Kedlaya came up with an algorithm for computing the zeta function of a hyperelliptic curve of genus g using Monsky-Washnitzer cohomology. This is a certain 2g-dimensional p-adic vector space on which a Frobenius operator lives. The characteristic polynomial of this operator yields then the zeta function. A few years later Lauder used in the context of determining the size of hypersurfaces an old result of Dwork concerning deformation. Deformation is a technique that looks at families of curves, where a specific fiber is easy to treat and the variation of Frobenius throughout the family satisfies a p-adic differential equation. Our work combines these two approaches and consists mainly of constructing a relative Monsky-Washnitzer cohomology (i.e. for one-dimensional families) for hyperelliptic curves and finding interesting forms of the corresponding differential equation. By taking well-chosen families E(G), so that E(0) is defined over a very small finite field, and solving the corresponding differential equation, we can construct an algorithm for a certain type of curves that uses far less memory than Kedlaya's and is also faster. An implementation in odd characteristic gives some very nice results. By reconsidering the solution technique of the differential equation and choosing other types of families we developed also an algorithm that works for any hyperelliptic curve and still requires far less memory than Kedlaya's algorithm. A final result concerns elliptic curves, where we showed that the Frobenius operator can be 'semi-diagonalized'. This allows a running time that is quadratic in the extension degree of the finite field and e.g. lets us compute the zeta function of an elliptic curve over a field of degree 100 and characteristic 3 in half a second. Het is bijzonder moeilijk om elektronische communicatie weg te denken uit onze moderne samenleving. De wetenschap die dit mogelijk maakt op een (min of meer) veilige manier is de cryptografie. Een groot deel van de cryptografische schema's is gebaseerd op de veronderstelde moeilijkheid van het berekenen van discrete logaritmes in eindige groepen: in goed gekozen groepen is het mogelijk heel snel een groot veelvoud n.P van een element P te bepalen, maar is het heel moeilijk deze operatie om te keren: uit P en n.P moet je dan n kunnen vinden. Om te bepalen of een groep bruikbaar is voor cryptografie, is het zeer belangrijk de grootte ervan te kennen. In deze thesis ontwikkelen we een p-adische cohomologie die toelaat algoritmes te ontwerpen die in staat zijn het aantal elementen in bepaalde soorten groepen te berekenen, namelijk elliptische krommen en jacobianen van hyperelliptische krommen over eindige velden. Beide soorten groepen worden intensief bestudeerd door cryptografen en wiskundigen en er bestaan reeds commercieel verkrijgbare producten die gebruik maken van elliptische krommen. De twee centrale begrippen in dit werk zijn Monsky-Washnitzer cohomologie -- deze laat toe de grootte van de kromme uit te drukken m.b.v. de matrix van een bepaalde afbeelding op een p-adische vectorruimte -- en deformatie. Deformatie is een techniek waarbij een ganse familie krommen tegelijk bekeken wordt: één kromme uit de familie is van bijzonder eenvoudige vorm en de verandering doorheen de familie kan worden weergegeven d.m.v. een p-adische differentiaalvergelijking. De idee is dan de 'moeilijke' kromme te deformeren tot een 'gemakkelijke' en via de differentiaalvergelijking resultaten terug te brengen tot de moeilijke. Door deze twee ideeën te combineren voor hyperelliptische krommen heb ik een p-adische relatieve cohomologie uitgewerkt die aanleiding geeft tot algoritmes die veel efficiënter zijn dan oudere bestaande, in het bijzonder wat betreft de hoeveelheid geheugen die gebruikt wordt. Voor elliptische krommen kunnen we dit aanpassen tot een uitzonderlijk snel algoritme dat de grootte van een kromme die mogelijkerwijze bruikbaar is voor cryptografie kan berekenen in een halve seconde.

Academic collection --- 681.3*G --- 512 --- Mathematics of computing --- Algebra --- Theses --- 512 Algebra --- 681.3*G Mathematics of computing