On the Use of the Negation Map in the Pollard Rho Method View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Joppe W. Bos , Thorsten Kleinjung , Arjen K. Lenstra

ABSTRACT

The negation map can be used to speed up the Pollard rho method to compute discrete logarithms in groups of elliptic curves over finite fields. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective alternative countermeasures. As a result, fruitless cycles can be resolved, but the best speedup we managed to achieve is by a factor of only 1.29. Although this is less than the speedup factor of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sqrt 2$\end{document} generally reported in the literature, it is supported by practical evidence. More... »

PAGES

66-82

References to SciGraph publications

  • 2001-05-18. CM-Curves with Good Cryptographic Properties in ADVANCES IN CRYPTOLOGY — CRYPTO ’91
  • 1999-01. Parallel Collision Search with Cryptanalytic Applications in JOURNAL OF CRYPTOLOGY
  • 1986. Use of Elliptic Curves in Cryptography in ADVANCES IN CRYPTOLOGY — CRYPTO ’85 PROCEEDINGS
  • 1999. Speeding up the Discrete Log Computation on Curves with Automorphisms in ADVANCES IN CRYPTOLOGY - ASIACRYPT’99
  • 2002-03-28. Faster Attacks on Elliptic Curve Cryptosystems in SELECTED AREAS IN CRYPTOGRAPHY
  • Book

    TITLE

    Algorithmic Number Theory

    ISBN

    978-3-642-14517-9
    978-3-642-14518-6

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-14518-6_9

    DOI

    http://dx.doi.org/10.1007/978-3-642-14518-6_9

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1022255302


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "Laboratory for Cryptologic Algorithms, EPFL, Station 14, CH-1015, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bos", 
            "givenName": "Joppe W.", 
            "id": "sg:person.011356726653.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011356726653.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "Laboratory for Cryptologic Algorithms, EPFL, Station 14, CH-1015, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kleinjung", 
            "givenName": "Thorsten", 
            "id": "sg:person.011764222665.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011764222665.65"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "Laboratory for Cryptologic Algorithms, EPFL, Station 14, CH-1015, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lenstra", 
            "givenName": "Arjen K.", 
            "id": "sg:person.011227631235.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011227631235.36"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1090/s0025-5718-1981-0606520-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003595162"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1978-0491431-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005983464"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-39799-x_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022380878", 
              "https://doi.org/10.1007/3-540-39799-x_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1987-0866109-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022745146"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-99-01119-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029013911"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-00-01213-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034045378"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-48000-6_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036129422", 
              "https://doi.org/10.1007/978-3-540-48000-6_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-48000-6_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036129422", 
              "https://doi.org/10.1007/978-3-540-48000-6_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/pl00003816", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040926849", 
              "https://doi.org/10.1007/pl00003816"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46766-1_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042501449", 
              "https://doi.org/10.1007/3-540-46766-1_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46766-1_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042501449", 
              "https://doi.org/10.1007/3-540-46766-1_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48892-8_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042673193", 
              "https://doi.org/10.1007/3-540-48892-8_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48892-8_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042673193", 
              "https://doi.org/10.1007/3-540-48892-8_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1987-0866113-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050650230"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2006496", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069694303"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "The negation map can be used to speed up the Pollard rho method to compute discrete logarithms in groups of elliptic curves over finite fields. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective alternative countermeasures. As a result, fruitless cycles can be resolved, but the best speedup we managed to achieve is by a factor of only 1.29. Although this is less than the speedup factor of \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$\\sqrt 2$\\end{document} generally reported in the literature, it is supported by practical evidence.", 
        "editor": [
          {
            "familyName": "Hanrot", 
            "givenName": "Guillaume", 
            "type": "Person"
          }, 
          {
            "familyName": "Morain", 
            "givenName": "Fran\u00e7ois", 
            "type": "Person"
          }, 
          {
            "familyName": "Thom\u00e9", 
            "givenName": "Emmanuel", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-14518-6_9", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-14517-9", 
            "978-3-642-14518-6"
          ], 
          "name": "Algorithmic Number Theory", 
          "type": "Book"
        }, 
        "name": "On the Use of the Negation Map in the Pollard Rho Method", 
        "pagination": "66-82", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1022255302"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-14518-6_9"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "6a075a5f46135387d34bf962c75c97b3920f100b6bf121691e3e393af37f4855"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-14518-6_9", 
          "https://app.dimensions.ai/details/publication/pub.1022255302"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:04", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29215_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-14518-6_9"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14518-6_9'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14518-6_9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14518-6_9'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14518-6_9'


     

    This table displays all metadata directly associated to this object as RDF triples.

    130 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-14518-6_9 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N3cbe69310a5440148f37e3b4677a8f44
    4 schema:citation sg:pub.10.1007/3-540-39799-x_31
    5 sg:pub.10.1007/3-540-46766-1_22
    6 sg:pub.10.1007/3-540-48892-8_15
    7 sg:pub.10.1007/978-3-540-48000-6_10
    8 sg:pub.10.1007/pl00003816
    9 https://doi.org/10.1090/s0025-5718-00-01213-8
    10 https://doi.org/10.1090/s0025-5718-1978-0491431-9
    11 https://doi.org/10.1090/s0025-5718-1981-0606520-5
    12 https://doi.org/10.1090/s0025-5718-1987-0866109-5
    13 https://doi.org/10.1090/s0025-5718-1987-0866113-7
    14 https://doi.org/10.1090/s0025-5718-99-01119-9
    15 https://doi.org/10.2307/2006496
    16 schema:datePublished 2010
    17 schema:datePublishedReg 2010-01-01
    18 schema:description The negation map can be used to speed up the Pollard rho method to compute discrete logarithms in groups of elliptic curves over finite fields. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective alternative countermeasures. As a result, fruitless cycles can be resolved, but the best speedup we managed to achieve is by a factor of only 1.29. Although this is less than the speedup factor of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sqrt 2$\end{document} generally reported in the literature, it is supported by practical evidence.
    19 schema:editor N6c30ba3a3d6c41218db986561e8ea9d6
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree true
    23 schema:isPartOf Nee67df8570fe4f3697dbcf251ca7ebb0
    24 schema:name On the Use of the Negation Map in the Pollard Rho Method
    25 schema:pagination 66-82
    26 schema:productId N035578eecdf54ff1a84fba313c4ea6e2
    27 N5040e8ea586c48fe9a09dc63694dcbfc
    28 Ncbd542c034ed459f99d7f639734db226
    29 schema:publisher N5c7f86ecbc454faaaf6c0a1374113eb1
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022255302
    31 https://doi.org/10.1007/978-3-642-14518-6_9
    32 schema:sdDatePublished 2019-04-16T08:04
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N12971376a64749be8f057ec950888be7
    35 schema:url https://link.springer.com/10.1007%2F978-3-642-14518-6_9
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N0265fad891244f8e9073e62268136ff5 rdf:first sg:person.011764222665.65
    40 rdf:rest Nf1787d1942064404a0921efb88a31767
    41 N035578eecdf54ff1a84fba313c4ea6e2 schema:name doi
    42 schema:value 10.1007/978-3-642-14518-6_9
    43 rdf:type schema:PropertyValue
    44 N12971376a64749be8f057ec950888be7 schema:name Springer Nature - SN SciGraph project
    45 rdf:type schema:Organization
    46 N29caa61a23e44d40b49d1cdd11903632 schema:familyName Thomé
    47 schema:givenName Emmanuel
    48 rdf:type schema:Person
    49 N3cbe69310a5440148f37e3b4677a8f44 rdf:first sg:person.011356726653.68
    50 rdf:rest N0265fad891244f8e9073e62268136ff5
    51 N4d4ce6bda4244819858b26c2dadb7c7a schema:familyName Hanrot
    52 schema:givenName Guillaume
    53 rdf:type schema:Person
    54 N5040e8ea586c48fe9a09dc63694dcbfc schema:name dimensions_id
    55 schema:value pub.1022255302
    56 rdf:type schema:PropertyValue
    57 N5c7f86ecbc454faaaf6c0a1374113eb1 schema:location Berlin, Heidelberg
    58 schema:name Springer Berlin Heidelberg
    59 rdf:type schema:Organisation
    60 N68822de778494230a96c620d4c606cb0 schema:familyName Morain
    61 schema:givenName François
    62 rdf:type schema:Person
    63 N6c30ba3a3d6c41218db986561e8ea9d6 rdf:first N4d4ce6bda4244819858b26c2dadb7c7a
    64 rdf:rest Na2bd6d5ab3df47c0b15be52ff719645d
    65 N963658f1801d44808447c74ae42b1556 rdf:first N29caa61a23e44d40b49d1cdd11903632
    66 rdf:rest rdf:nil
    67 Na2bd6d5ab3df47c0b15be52ff719645d rdf:first N68822de778494230a96c620d4c606cb0
    68 rdf:rest N963658f1801d44808447c74ae42b1556
    69 Ncbd542c034ed459f99d7f639734db226 schema:name readcube_id
    70 schema:value 6a075a5f46135387d34bf962c75c97b3920f100b6bf121691e3e393af37f4855
    71 rdf:type schema:PropertyValue
    72 Nee67df8570fe4f3697dbcf251ca7ebb0 schema:isbn 978-3-642-14517-9
    73 978-3-642-14518-6
    74 schema:name Algorithmic Number Theory
    75 rdf:type schema:Book
    76 Nf1787d1942064404a0921efb88a31767 rdf:first sg:person.011227631235.36
    77 rdf:rest rdf:nil
    78 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    79 schema:name Mathematical Sciences
    80 rdf:type schema:DefinedTerm
    81 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Pure Mathematics
    83 rdf:type schema:DefinedTerm
    84 sg:person.011227631235.36 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    85 schema:familyName Lenstra
    86 schema:givenName Arjen K.
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011227631235.36
    88 rdf:type schema:Person
    89 sg:person.011356726653.68 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    90 schema:familyName Bos
    91 schema:givenName Joppe W.
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011356726653.68
    93 rdf:type schema:Person
    94 sg:person.011764222665.65 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    95 schema:familyName Kleinjung
    96 schema:givenName Thorsten
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011764222665.65
    98 rdf:type schema:Person
    99 sg:pub.10.1007/3-540-39799-x_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022380878
    100 https://doi.org/10.1007/3-540-39799-x_31
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/3-540-46766-1_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042501449
    103 https://doi.org/10.1007/3-540-46766-1_22
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/3-540-48892-8_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042673193
    106 https://doi.org/10.1007/3-540-48892-8_15
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/978-3-540-48000-6_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036129422
    109 https://doi.org/10.1007/978-3-540-48000-6_10
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/pl00003816 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040926849
    112 https://doi.org/10.1007/pl00003816
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1090/s0025-5718-00-01213-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034045378
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1090/s0025-5718-1978-0491431-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005983464
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1090/s0025-5718-1981-0606520-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003595162
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1090/s0025-5718-1987-0866109-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022745146
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1090/s0025-5718-1987-0866113-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050650230
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1090/s0025-5718-99-01119-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029013911
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.2307/2006496 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069694303
    127 rdf:type schema:CreativeWork
    128 https://www.grid.ac/institutes/grid.5333.6 schema:alternateName École Polytechnique Fédérale de Lausanne
    129 schema:name Laboratory for Cryptologic Algorithms, EPFL, Station 14, CH-1015, Lausanne, Switzerland
    130 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...