Pollard's kangaroo algorithm (original) (raw)
La méthode des kangourous permet de résoudre le problème du logarithme discret, elle est due à John M. Pollard, et a été publiée en 1978. Il ne doit pas être confondu avec l'algorithme rho de Pollard pour les logarithmes, bien que publié dans le même papier par John M. Pollard en 1978. Il s'agit d'une variante de l'algorithme rho de Pollard, basée sur un résultat de probabilités du paradoxe des anniversaires. De ce fait, l'algorithme n'est pas déterministe.
| Property | Value |
|---|---|
| dbo:abstract | La méthode des kangourous permet de résoudre le problème du logarithme discret, elle est due à John M. Pollard, et a été publiée en 1978. Il ne doit pas être confondu avec l'algorithme rho de Pollard pour les logarithmes, bien que publié dans le même papier par John M. Pollard en 1978. Il s'agit d'une variante de l'algorithme rho de Pollard, basée sur un résultat de probabilités du paradoxe des anniversaires. De ce fait, l'algorithme n'est pas déterministe. (fr) In computational number theory and computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see below) is an algorithm for solving the discrete logarithm problem. The algorithm was introduced in 1978 by the number theorist J. M. Pollard, in the same paper as his better-known Pollard's rho algorithm for solving the same problem. Although Pollard described the application of his algorithm to the discrete logarithm problem in the multiplicative group of units modulo a prime p, it is in fact a generic discrete logarithm algorithm—it will work in any finite cyclic group. (en) Pollards lambda-algoritme, ook bekend onder de naam Pollards kangoeroe-algoritme, is een algoritme om de discrete logaritme te vinden. De Britse wiskundige John Pollard beschreef deze methode in hetzelfde artikel als waarin hij Pollards rho-algoritme voor logaritmen beschreef. Pollards lambda-algoritme is bruikbaar om de discrete logaritme te bepalen, als men weet dat deze tot een beperkt aantal waarden behoort. Door en te stellen is het mogelijk om het Pollard lambda-algoritme voor algemene te gebruiken, maar Pollards lambda-algoritme gaat veel sneller als een relatief klein aantal waarden bevat. (nl) В и вычислительной алгебре алгоритм «кенгуру» Полларда (а также лямбда-алгоритм Полларда, см. раздел «» ниже) — это алгоритм решения задачи дискретного логарифмирования. Алгоритм был предложен в 1978 специалистом в области теории чисел в той же статье, что и его более известный ρ-алгоритм для решения той же задачи. Хотя Поллард описывает применение этого алгоритма для задачи дискретного логарифмирования в мультипликативной группе по модулю простого p, он является, фактически, общим алгоритмом дискретного логарифмирования — он будет работать на любой циклической конечной группе. (ru) |
| dbo:wikiPageID | 12928899 (xsd:integer) |
| dbo:wikiPageLength | 5969 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1113480716 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Scientific_American dbr:Algorithm dbr:Index_calculus_algorithm dbr:Computer_algebra dbc:Number_theoretic_algorithms dbr:Greek_letter dbr:Pseudorandom dbr:Computational_complexity_theory dbr:Computational_number_theory dbc:Logarithms dbr:Discrete_logarithm dbr:John_Pollard_(mathematician) dbr:Pollard's_rho_algorithm_for_logarithms dbr:Rainbow_table dbc:Computer_algebra dbr:Kangaroo dbr:Lambda dbr:Bit dbr:Treadmill dbr:RSA_(algorithm) dbr:Exponential_time dbr:Public_key_cryptosystem dbr:Subexponential_time |
| dbp:wikiPageUsesTemplate | dbt:Number-theoretic_algorithms dbt:Reflist |
| dct:subject | dbc:Number_theoretic_algorithms dbc:Logarithms dbc:Computer_algebra |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatLogarithms yago:WikicatNumberTheoreticAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Exponent106812417 yago:Logarithm106812631 yago:MathematicalNotation106808720 yago:Notation106808493 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:Writing106359877 yago:WrittenCommunication106349220 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment | La méthode des kangourous permet de résoudre le problème du logarithme discret, elle est due à John M. Pollard, et a été publiée en 1978. Il ne doit pas être confondu avec l'algorithme rho de Pollard pour les logarithmes, bien que publié dans le même papier par John M. Pollard en 1978. Il s'agit d'une variante de l'algorithme rho de Pollard, basée sur un résultat de probabilités du paradoxe des anniversaires. De ce fait, l'algorithme n'est pas déterministe. (fr) In computational number theory and computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see below) is an algorithm for solving the discrete logarithm problem. The algorithm was introduced in 1978 by the number theorist J. M. Pollard, in the same paper as his better-known Pollard's rho algorithm for solving the same problem. Although Pollard described the application of his algorithm to the discrete logarithm problem in the multiplicative group of units modulo a prime p, it is in fact a generic discrete logarithm algorithm—it will work in any finite cyclic group. (en) В и вычислительной алгебре алгоритм «кенгуру» Полларда (а также лямбда-алгоритм Полларда, см. раздел «» ниже) — это алгоритм решения задачи дискретного логарифмирования. Алгоритм был предложен в 1978 специалистом в области теории чисел в той же статье, что и его более известный ρ-алгоритм для решения той же задачи. Хотя Поллард описывает применение этого алгоритма для задачи дискретного логарифмирования в мультипликативной группе по модулю простого p, он является, фактически, общим алгоритмом дискретного логарифмирования — он будет работать на любой циклической конечной группе. (ru) Pollards lambda-algoritme, ook bekend onder de naam Pollards kangoeroe-algoritme, is een algoritme om de discrete logaritme te vinden. De Britse wiskundige John Pollard beschreef deze methode in hetzelfde artikel als waarin hij Pollards rho-algoritme voor logaritmen beschreef. Pollards lambda-algoritme is bruikbaar om de discrete logaritme te bepalen, als men weet dat deze tot een beperkt aantal waarden behoort. (nl) |
| rdfs:label | Méthode des kangourous de Pollard (fr) Pollard's kangaroo algorithm (en) Pollards lambda-algoritme (nl) Алгоритм «кенгуру» Полларда (ru) |
| owl:sameAs | freebase:Pollard's kangaroo algorithm yago-res:Pollard's kangaroo algorithm wikidata:Pollard's kangaroo algorithm dbpedia-fr:Pollard's kangaroo algorithm dbpedia-nl:Pollard's kangaroo algorithm dbpedia-ru:Pollard's kangaroo algorithm https://global.dbpedia.org/id/qFVA |
| prov:wasDerivedFrom | wikipedia-en:Pollard's_kangaroo_algorithm?oldid=1113480716&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Pollard's_kangaroo_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Pollard |
| is dbo:wikiPageRedirects of | dbr:Pollard's_kangaroo_method dbr:Pollard's_lambda_algorithm dbr:Pollard_kangaroo dbr:Kangaroo_algorithm |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Cycle_detection dbr:Index_of_logarithm_articles dbr:Pollard dbr:Discrete_logarithm dbr:John_Pollard_(mathematician) dbr:Rainbow_table dbr:Discrete_logarithm_records dbr:Pollard's_rho_algorithm dbr:Pollard's_kangaroo_method dbr:Pollard's_lambda_algorithm dbr:Pollard_kangaroo dbr:Kangaroo_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Pollard's_kangaroo_algorithm |