| dbo:abstract
|
- El algoritmo rho de Pollard para el logaritmo discreto es un algoritmo publicado por el matemático en 1978 que permite resolver el problema del logaritmo discreto en cualquier grupo. La idea para este algoritmo es similar a la que se utiliza en otro para la factorización de enteros, publicado por Pollard en 1975 (algoritmo rho de Pollard). Existen algoritmos de orden subexponencial para el problema del logaritmo discreto en (por ejemplo, el ) y el algoritmo de Pollard no lo es, pese a lo cual es útil en la práctica debido a ser simple y efectivo para grupos pequeños. Además tiene la ventaja de no utilizar nada de la estructura de un grupo particular. (es)
- L'algorithme rho de Pollard a été introduit par John M. Pollard en 1978 pour résoudre le problème du logarithme discret. Il est analogue à l'algorithme rho de Pollard que le même auteur avait introduit pour résoudre le problème factorisation entière. (fr)
- Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem. The goal is to compute such that , where belongs to a cyclic group generated by . The algorithm computes integers , , , and such that . If the underlying group is cyclic of order , by substituting as and noting that two powers are equal if and only if the exponents are equivalent modulo the order of the base, in this case modulo , we get that is one of the solutions of the equation . Solutions to this equation are easily obtained using the extended Euclidean algorithm. To find the needed , , , and the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence , where the function is assumed to be random-looking and thus is likely to enter into a loop of approximate length after steps. One way to define such a function is to use the following rules: Divide into three of approximately equal size: , , and . If is in then double both and ; if then increment , if then increment . (en)
- ポラード・ロー離散対数アルゴリズム （ポラード・ローりさんたいすうアルゴリズム、英語: Pollard's rho algorithm for logarithms）は（英語: John Pollard）が1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。 このアルゴリズムの目的は、αが生成する巡回群Gとその元βに対し、となるγを求めることにある。そのためにまず、このアルゴリズムは となるa, b, A, Bを求める。巡回群の位数nが既知の場合、γは方程式の解として求まる。 a, b, A, Bを求めるにはフロイドの循環検出法を用いて、数列のサイクルを検出する。この数列は、関数を用いて計算できるように選ぶ。fが十分にランダムなら、この数列は平均ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる：まず、Gを大きさがほぼ等しい3つの集合, , の非交和に分割する。のときはaとbをそれぞれ2倍する。のときはaをインクリメントする。のときはbをインクリメントする。 (ja)
- Pollards rho-algoritme is een algoritme dat door John Pollard in 1978 beschreven werd om de discrete logaritme zoals dat is gedefinieerd in een cyclische groep te berekenen.Het grote voordeel ten opzichte van het Baby-steps giant-steps-algoritme is dat voor deze methode geen opslagruimte nodig is. (nl)
- ро-метод Полларда для дискретного логарифмирования (-метод) — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Предложен британским математиком (англ. John Pollard) в 1978 году, основные идеи алгоритма очень похожи на идеи ро-алгоритма Полларда для . Данный метод рассматривается для группы ненулевых вычетов по модулю , где — простое число, большее . (ru)
- 离散对数的波拉德ρ算法是1978年所发明解决离散对数问题的算法。 算法的目标是求 使得 ，其中 属于一个由 生成的 循环群 。该算法寻找 , , , 使得 。若他们基于的群是一个 阶的循环群，则 是方程 的其中一个解。 为求得 , , , ， 该算法使用 Floyd判圈算法 在数列 中寻找一个环。 假设映射 是近似于随机的，则有可能在约 步后发现一个环。可使用一下规则来生成一个此类映射：将 分割为三个不相交的子集 ，， ，且其所含元素数量大致相等，如果 则将 和 加倍； 如果 则将 自增； 如果 则将 自增。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 6950 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- L'algorithme rho de Pollard a été introduit par John M. Pollard en 1978 pour résoudre le problème du logarithme discret. Il est analogue à l'algorithme rho de Pollard que le même auteur avait introduit pour résoudre le problème factorisation entière. (fr)
- ポラード・ロー離散対数アルゴリズム （ポラード・ローりさんたいすうアルゴリズム、英語: Pollard's rho algorithm for logarithms）は（英語: John Pollard）が1978年に導入した離散対数問題のアルゴリズムであり、ポラード・ロー素因数分解法と似た構造を持つ。 このアルゴリズムの目的は、αが生成する巡回群Gとその元βに対し、となるγを求めることにある。そのためにまず、このアルゴリズムは となるa, b, A, Bを求める。巡回群の位数nが既知の場合、γは方程式の解として求まる。 a, b, A, Bを求めるにはフロイドの循環検出法を用いて、数列のサイクルを検出する。この数列は、関数を用いて計算できるように選ぶ。fが十分にランダムなら、この数列は平均ステップでループに入る。このような関数は、例えば以下のようにすれば定義できる：まず、Gを大きさがほぼ等しい3つの集合, , の非交和に分割する。のときはaとbをそれぞれ2倍する。のときはaをインクリメントする。のときはbをインクリメントする。 (ja)
- Pollards rho-algoritme is een algoritme dat door John Pollard in 1978 beschreven werd om de discrete logaritme zoals dat is gedefinieerd in een cyclische groep te berekenen.Het grote voordeel ten opzichte van het Baby-steps giant-steps-algoritme is dat voor deze methode geen opslagruimte nodig is. (nl)
- ро-метод Полларда для дискретного логарифмирования (-метод) — алгоритм дискретного логарифмирования в кольце вычетов по простому модулю, имеющий экспоненциальную сложность. Предложен британским математиком (англ. John Pollard) в 1978 году, основные идеи алгоритма очень похожи на идеи ро-алгоритма Полларда для . Данный метод рассматривается для группы ненулевых вычетов по модулю , где — простое число, большее . (ru)
- 离散对数的波拉德ρ算法是1978年所发明解决离散对数问题的算法。 算法的目标是求 使得 ，其中 属于一个由 生成的 循环群 。该算法寻找 , , , 使得 。若他们基于的群是一个 阶的循环群，则 是方程 的其中一个解。 为求得 , , , ， 该算法使用 Floyd判圈算法 在数列 中寻找一个环。 假设映射 是近似于随机的，则有可能在约 步后发现一个环。可使用一下规则来生成一个此类映射：将 分割为三个不相交的子集 ，， ，且其所含元素数量大致相等，如果 则将 和 加倍； 如果 则将 自增； 如果 则将 自增。 (zh)
- El algoritmo rho de Pollard para el logaritmo discreto es un algoritmo publicado por el matemático en 1978 que permite resolver el problema del logaritmo discreto en cualquier grupo. La idea para este algoritmo es similar a la que se utiliza en otro para la factorización de enteros, publicado por Pollard en 1975 (algoritmo rho de Pollard). (es)
- Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem. (en)
|
| rdfs:label
|
- Algoritmo rho de Pollard (logaritmos discretos) (es)
- Algorithme rho de Pollard (logarithme discret) (fr)
- ポラード・ロー離散対数アルゴリズム (ja)
- Pollard's rho algorithm for logarithms (en)
- Pollards rho-algoritme (nl)
- Ро-метод Полларда для дискретного логарифмирования (ru)
- 离散对数的波拉德ρ算法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
