| dbo:abstract
|
- Der Pohlig-Hellman-Algorithmus wurde nach den Mathematikern und Martin Hellman benannt. Gelegentlich ist dieser Algorithmus in der Literatur auch unter dem Namen Silver-Pohlig-Hellman-Algorithmus zu finden. Mit dem Pohlig-Hellman-Algorithmus kann der diskrete Logarithmus in einer zyklischen Gruppe berechnet werden. Die Relevanz dieses Verfahrens liegt darin, dass der Rechenaufwand nicht von der Gruppenordnung, sondern vom größten Faktor der Gruppenordnung abhängt. Nachteilig ist, dass für dieses Verfahren eine Primfaktorzerlegung der Gruppenordnung bekannt sein muss. Solch eine Primfaktorzerlegung ist im Allgemeinen jedoch nur sehr schwer zu bestimmen. (de)
- In group theory, the Pohlig–Hellman algorithm, sometimes credited as the Silver–Pohlig–Hellman algorithm, is a special-purpose algorithm for computing discrete logarithms in a finite abelian group whose order is a smooth integer. The algorithm was introduced by Roland Silver, but first published by Stephen Pohlig and Martin Hellman (independent of Silver). (en)
- L’algorithme de Pohlig-Hellman est un algorithme pour résoudre le problème du logarithme discret (PLD). Il divise un PLD en sous-problèmes (tous des PLD aussi) et utilise ensuite les résultats de ces sous-problèmes pour construire la solution. (fr)
- Het Pohlig-Hellman algoritme is een algoritme om de discrete logaritme zoals die is gedefinieerd in een cyclische groep, te berekenen. In het bijzonder vindt het algoritme toepassing op de van een eindig lichaam . Als het product is van kleine priemfactoren, noemt men het getal glad en is het Polig-Hellman-algoritme een geschikte methode om deze discrete logaritme te berekenen. Het algoritme werd ontwikkeld door , maar voor het eerst, onafhankelijk van Silver, gepubliceerd door en . Het belang van deze methode is dat de hoeveelheid rekenwerk niet afhangt van de orde van de groep, maar van de grootste factor in de orde. Het nadeel is dat de orde gefactoriseerd moet worden in priemfactoren en een dergelijke factorisatie in het algemeen moeilijk vast te stellen is. (nl)
- Redukcja Pohliga-Hellmana jest metodą obliczania logarytmu dyskretnego w ciele skończonym GF(p) wymyśloną przez i Martina Hellmana. Jeżeli mamy ciało skończone o elementach, rząd jego grupy multiplikatywnej wynosi Szukamy takiego że: gdzie jest generatorem grupy multiplikatywnej tego ciała, a elementem tego ciała. KROK 1: Redukujemy DLP (ang. discrete logarithm problem) do analogicznego zagadnienia w grupach rzędu Dla każdego obliczamy: Z kongruencji: możemy łatwo otrzymać układ kongruencji: (poszczególne można otrzymać jako ), które następnie możemy rozwiązać przy pomocy chińskiego twierdzenia o resztach. KROK 2: Jeżeli w rozkładzie występuje jakaś duża potęga liczby pierwszej redukujemy DLP w grupie rzędu do kilku problemów w grupach rzędu Przyjmijmy i oraz Wówczas: Podnosząc obie strony kongruencji do potęgi możemy obliczyć następnie znów zapisujemy kongruencję: i podnosząc obie strony do potęgi otrzymamy itd. Mając wszystkie otrzymamy: Redukcja P-H pozwala na szybkie rozwiązanie DLP, o ile ma w rozkładzie na czynniki pierwsze małe liczby pierwsze. Stąd jeżeli kryptosystem oparty na zagadnieniu logarytmu dyskretnego ma być bezpieczny, jeżeli opiera się na grupach to musi mieć w rozkładzie na czynniki pierwsze co najmniej jedną dużą liczbę pierwszą. Stąd często obiera się jako liczbę postaci gdzie zarówno jak i są pierwsze. które posiadają taką własność, nazywa się liczbami pierwszymi Sophie Germain. (pl)
- Алгоритм Полига — Хеллмана (также называемый алгоритм Сильвера — Полига — Хеллмана) — детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностей алгоритма является то, что для простых чисел специального вида можно находить дискретный логарифм за полиномиальное время. (ru)
- Алгоритм Поліґа-Геллмана (англ. Pohlig–Hellman algorithm) — спеціалізований алгоритм, який отримує перевагу від факторизації порядку мультиплікативної групи де — гладке число. Нехай буде розкладом на прості множники. Якщо тоді підхід полягає в визначенні для і тоді отримання Кожен з визначається обчисленням цифр для його -арного представлення: де (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 6433 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In group theory, the Pohlig–Hellman algorithm, sometimes credited as the Silver–Pohlig–Hellman algorithm, is a special-purpose algorithm for computing discrete logarithms in a finite abelian group whose order is a smooth integer. The algorithm was introduced by Roland Silver, but first published by Stephen Pohlig and Martin Hellman (independent of Silver). (en)
- L’algorithme de Pohlig-Hellman est un algorithme pour résoudre le problème du logarithme discret (PLD). Il divise un PLD en sous-problèmes (tous des PLD aussi) et utilise ensuite les résultats de ces sous-problèmes pour construire la solution. (fr)
- Алгоритм Полига — Хеллмана (также называемый алгоритм Сильвера — Полига — Хеллмана) — детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностей алгоритма является то, что для простых чисел специального вида можно находить дискретный логарифм за полиномиальное время. (ru)
- Алгоритм Поліґа-Геллмана (англ. Pohlig–Hellman algorithm) — спеціалізований алгоритм, який отримує перевагу від факторизації порядку мультиплікативної групи де — гладке число. Нехай буде розкладом на прості множники. Якщо тоді підхід полягає в визначенні для і тоді отримання Кожен з визначається обчисленням цифр для його -арного представлення: де (uk)
- Der Pohlig-Hellman-Algorithmus wurde nach den Mathematikern und Martin Hellman benannt. Gelegentlich ist dieser Algorithmus in der Literatur auch unter dem Namen Silver-Pohlig-Hellman-Algorithmus zu finden. Mit dem Pohlig-Hellman-Algorithmus kann der diskrete Logarithmus in einer zyklischen Gruppe berechnet werden. (de)
- Het Pohlig-Hellman algoritme is een algoritme om de discrete logaritme zoals die is gedefinieerd in een cyclische groep, te berekenen. In het bijzonder vindt het algoritme toepassing op de van een eindig lichaam . Als het product is van kleine priemfactoren, noemt men het getal glad en is het Polig-Hellman-algoritme een geschikte methode om deze discrete logaritme te berekenen. Het algoritme werd ontwikkeld door , maar voor het eerst, onafhankelijk van Silver, gepubliceerd door en . (nl)
- Redukcja Pohliga-Hellmana jest metodą obliczania logarytmu dyskretnego w ciele skończonym GF(p) wymyśloną przez i Martina Hellmana. Jeżeli mamy ciało skończone o elementach, rząd jego grupy multiplikatywnej wynosi Szukamy takiego że: gdzie jest generatorem grupy multiplikatywnej tego ciała, a elementem tego ciała. KROK 1: Redukujemy DLP (ang. discrete logarithm problem) do analogicznego zagadnienia w grupach rzędu Dla każdego obliczamy: Z kongruencji: możemy łatwo otrzymać układ kongruencji: (poszczególne można otrzymać jako ), Przyjmijmy i oraz Wówczas: Mając wszystkie otrzymamy: (pl)
|
| rdfs:label
|
- Pohlig-Hellman-Algorithmus (de)
- Algorithme de Pohlig-Hellman (fr)
- Pohlig–Hellman algorithm (en)
- Pohlig-Hellman-algoritme (nl)
- Redukcja Pohliga-Hellmana (pl)
- Алгоритм Полига — Хеллмана (ru)
- Алгоритм Поліґа-Геллмана (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
