Efficient pairing computation with theta functions
Identifieur interne : 001F03 ( Hal/Corpus ); précédent : 001F02; suivant : 001F04Efficient pairing computation with theta functions
Auteurs : David Lubicz ; Damien RobertSource :
Abstract
In this paper, we present a new approach based on theta functions to compute Weil and Tate pairings. A benefit of our method, which does not rely on the classical Miller's algorithm, is its generality since it extends to all abelian varieties the classical Weil and Tate pairing formulas. In the case of dimension $1$ and $2$ abelian varieties our algorithms lead to implementations which are efficient and naturally deterministic. We also introduce symmetric Weil and Tate pairings on Kummer varieties and explain how to compute them efficiently. We exhibit a nice algorithmic compatibility between some algebraic groups quotiented by the action of the automorphism $-1$, where the $\Z$-action can be computed efficiently with a Montgomery ladder type algorithm.
Url:
DOI: 10.1007/978-3-642-14518-6_21
Links to Exploration step
Hal:hal-00528944Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient pairing computation with theta functions</title>
<author><name sortKey="Lubicz, David" sort="Lubicz, David" uniqKey="Lubicz D" first="David" last="Lubicz">David Lubicz</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-75" status="VALID"><orgName>Institut de Recherche Mathématique de Rennes</orgName>
<orgName type="acronym">IRMAR</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://irmar.univ-rennes1.fr/</ref>
</desc>
<listRelation><relation active="#struct-406201" type="direct"></relation>
<relation active="#struct-105160" type="direct"></relation>
<relation name="- RENNES" active="#struct-301232" type="direct"></relation>
<relation active="#struct-6862" type="direct"></relation>
<relation name="UMR6625" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-406201" type="direct"><org type="institution" xml:id="struct-406201" status="VALID"><orgName>Université Rennes 2</orgName>
<desc><address><addrLine>Place du recteur Henri Le Moal - CS 24307 - 35043 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes2.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-105160" type="direct"><org type="institution" xml:id="struct-105160" status="VALID"><orgName>Université de Rennes 1</orgName>
<orgName type="acronym">UR1</orgName>
<desc><address><addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="- RENNES" active="#struct-301232" type="direct"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-6862" type="direct"><org type="institution" xml:id="struct-6862" status="VALID"><orgName>École normale supérieure - Cachan</orgName>
<orgName type="acronym">ENS Cachan</orgName>
<desc><address><addrLine>61, avenue du Président Wilson - 94230 Cachan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ens-cachan.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR6625" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Robert, Damien" sort="Robert, Damien" uniqKey="Robert D" first="Damien" last="Robert">Damien Robert</name>
<affiliation><hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID"><idno type="RNSR">201020971F</idno>
<orgName>Cryptology, Arithmetic: Hardware and Software</orgName>
<orgName type="acronym">CARAMEL</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/caramel</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00528944</idno>
<idno type="halId">hal-00528944</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00528944</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00528944</idno>
<idno type="doi">10.1007/978-3-642-14518-6_21</idno>
<date when="2010-07-19">2010-07-19</date>
<idno type="wicri:Area/Hal/Corpus">001F03</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Efficient pairing computation with theta functions</title>
<author><name sortKey="Lubicz, David" sort="Lubicz, David" uniqKey="Lubicz D" first="David" last="Lubicz">David Lubicz</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-75" status="VALID"><orgName>Institut de Recherche Mathématique de Rennes</orgName>
<orgName type="acronym">IRMAR</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://irmar.univ-rennes1.fr/</ref>
</desc>
<listRelation><relation active="#struct-406201" type="direct"></relation>
<relation active="#struct-105160" type="direct"></relation>
<relation name="- RENNES" active="#struct-301232" type="direct"></relation>
<relation active="#struct-6862" type="direct"></relation>
<relation name="UMR6625" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-406201" type="direct"><org type="institution" xml:id="struct-406201" status="VALID"><orgName>Université Rennes 2</orgName>
<desc><address><addrLine>Place du recteur Henri Le Moal - CS 24307 - 35043 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes2.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-105160" type="direct"><org type="institution" xml:id="struct-105160" status="VALID"><orgName>Université de Rennes 1</orgName>
<orgName type="acronym">UR1</orgName>
<desc><address><addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes1.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="- RENNES" active="#struct-301232" type="direct"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-6862" type="direct"><org type="institution" xml:id="struct-6862" status="VALID"><orgName>École normale supérieure - Cachan</orgName>
<orgName type="acronym">ENS Cachan</orgName>
<desc><address><addrLine>61, avenue du Président Wilson - 94230 Cachan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.ens-cachan.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR6625" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Robert, Damien" sort="Robert, Damien" uniqKey="Robert D" first="Damien" last="Robert">Damien Robert</name>
<affiliation><hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID"><idno type="RNSR">201020971F</idno>
<orgName>Cryptology, Arithmetic: Hardware and Software</orgName>
<orgName type="acronym">CARAMEL</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/caramel</ref>
</desc>
<listRelation><relation active="#struct-129671" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-423083" type="direct"></relation>
<relation active="#struct-206040" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno>
<orgName>INRIA Nancy - Grand Est</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/nancy</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName>
<orgName type="acronym">LORIA - ALGO</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref>
</desc>
<listRelation><relation active="#struct-206040" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-413289" type="indirect"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1007/978-3-642-14518-6_21</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">In this paper, we present a new approach based on theta functions to compute Weil and Tate pairings. A benefit of our method, which does not rely on the classical Miller's algorithm, is its generality since it extends to all abelian varieties the classical Weil and Tate pairing formulas. In the case of dimension $1$ and $2$ abelian varieties our algorithms lead to implementations which are efficient and naturally deterministic. We also introduce symmetric Weil and Tate pairings on Kummer varieties and explain how to compute them efficiently. We exhibit a nice algorithmic compatibility between some algebraic groups quotiented by the action of the automorphism $-1$, where the $\Z$-action can be computed efficiently with a Montgomery ladder type algorithm.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">Efficient pairing computation with theta functions</title>
<author role="aut"><persName><forename type="first">David</forename>
<surname>Lubicz</surname>
</persName>
<email></email>
<idno type="halauthor">297219</idno>
<affiliation ref="#struct-75"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Damien</forename>
<surname>Robert</surname>
</persName>
<email>damien.robert@loria.fr</email>
<idno type="idhal">damien-robert</idno>
<idno type="halauthor">440738</idno>
<affiliation ref="#struct-119560"></affiliation>
</author>
<editor role="depositor"><persName><forename>Damien</forename>
<surname>Robert</surname>
</persName>
<email>damien.robert@inria.fr</email>
</editor>
<funder ref="#projanr-11145"></funder>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2010-10-23 00:38:04</date>
<date type="whenWritten">2010-07</date>
<date type="whenModified">2015-12-15 17:18:22</date>
<date type="whenReleased">2010-10-24 07:32:35</date>
<date type="whenProduced">2010-07-19</date>
<date type="whenEndEmbargoed">2010-10-23</date>
<ref type="file" target="https://hal.archives-ouvertes.fr/hal-00528944/document"><date notBefore="2010-10-23"></date>
</ref>
<ref type="file" subtype="author" n="1" target="https://hal.archives-ouvertes.fr/hal-00528944/file/pairing_short.pdf"><date notBefore="2010-10-23"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="139097"><persName><forename>Damien</forename>
<surname>Robert</surname>
</persName>
<email>damien.robert@inria.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">hal-00528944</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00528944</idno>
<idno type="halBibtex">lubicz:hal-00528944</idno>
<idno type="halRefHtml">Guillaume Hanrot and François Morain and Emmanuel Thomé. ANTS IX - Algorithmic Number Theory 2010, Jul 2010, Nancy, France. Springer-Verlag, 6197, pp.251-269, 2010, Lecture Notes in Computer Science. <10.1007/978-3-642-14518-6_21></idno>
<idno type="halRef">Guillaume Hanrot and François Morain and Emmanuel Thomé. ANTS IX - Algorithmic Number Theory 2010, Jul 2010, Nancy, France. Springer-Verlag, 6197, pp.251-269, 2010, Lecture Notes in Computer Science. <10.1007/978-3-642-14518-6_21></idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="UNIV-RENNES1">Université de Rennes 1</idno>
<idno type="stamp" n="INSA-RENNES">Institut National des Sciences Appliquées de Rennes</idno>
<idno type="stamp" n="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="INSMI">CNRS-INSMI - INstitut des Sciences Mathématiques et de leurs Interactions</idno>
<idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="LORIA-ACGI" p="LORIA">Algorithmique, calcul, image et géométrie</idno>
<idno type="stamp" n="IRMAR-GAR" p="IRMAR">Géométrie algébrique réelle</idno>
<idno type="stamp" n="IRMAR">Institut de Recherche Mathématique de Rennes</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="IRMAR-GAE" p="IRMAR">Géométrie et algèbre effectives </idno>
<idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="UR2-HB">Université Rennes 2 - Haute Bretagne</idno>
<idno type="stamp" n="INRIA2">INRIA 2</idno>
<idno type="stamp" n="LORIA-ALGO-TEST5">LORIA-ALGO-TEST5 </idno>
</seriesStmt>
<notesStmt><note type="commentary">The original publication is available at www.springerlink.com</note>
<note type="audience" n="2">International</note>
<note type="invited" n="0">No</note>
<note type="popular" n="0">No</note>
<note type="peer" n="1">Yes</note>
<note type="proceedings" n="1">Yes</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Efficient pairing computation with theta functions</title>
<author role="aut"><persName><forename type="first">David</forename>
<surname>Lubicz</surname>
</persName>
<idno type="halAuthorId">297219</idno>
<affiliation ref="#struct-75"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Damien</forename>
<surname>Robert</surname>
</persName>
<email>damien.robert@loria.fr</email>
<idno type="idHal">damien-robert</idno>
<idno type="halAuthorId">440738</idno>
<affiliation ref="#struct-119560"></affiliation>
</author>
</analytic>
<monogr><title level="m">Algorithmic Number Theory 9th International Symposium, Nancy, France, ANTS-IX, July 19-23, 2010, Proceedings</title>
<meeting><title>ANTS IX - Algorithmic Number Theory 2010</title>
<date type="start">2010-07-19</date>
<date type="end">2010-07-23</date>
<settlement>Nancy</settlement>
<country key="FR">France</country>
</meeting>
<editor>Guillaume Hanrot and François Morain and Emmanuel Thomé</editor>
<imprint><publisher>Springer-Verlag</publisher>
<biblScope unit="serie">Lecture Notes in Computer Science</biblScope>
<biblScope unit="volume">6197</biblScope>
<biblScope unit="pp">251-269</biblScope>
<date type="datePub">2010</date>
</imprint>
</monogr>
<idno type="doi">10.1007/978-3-642-14518-6_21</idno>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="en">English</language>
</langUsage>
<textClass><classCode scheme="halDomain" n="info.info-sc">Computer Science [cs]/Symbolic Computation [cs.SC]</classCode>
<classCode scheme="halTypology" n="COMM">Conference papers</classCode>
</textClass>
<abstract xml:lang="en">In this paper, we present a new approach based on theta functions to compute Weil and Tate pairings. A benefit of our method, which does not rely on the classical Miller's algorithm, is its generality since it extends to all abelian varieties the classical Weil and Tate pairing formulas. In the case of dimension $1$ and $2$ abelian varieties our algorithms lead to implementations which are efficient and naturally deterministic. We also introduce symmetric Weil and Tate pairings on Kummer varieties and explain how to compute them efficiently. We exhibit a nice algorithmic compatibility between some algebraic groups quotiented by the action of the automorphism $-1$, where the $\Z$-action can be computed efficiently with a Montgomery ladder type algorithm.</abstract>
</profileDesc>
</hal>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001F03 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 001F03 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Hal |étape= Corpus |type= RBID |clé= Hal:hal-00528944 |texte= Efficient pairing computation with theta functions }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |