Pohlig–Hellman algorithm: Difference between revisions

Revision as of 06:26, 5 June 2024

Latest revision as of 18:44, 19 October 2024

(One intermediate revision by one other user not shown)

Line 34:

:# Solve the simultaneous congruence <math display="block">x\equiv x_i\pmod{p_i^{e_i}}

\quad\forall i\in\{1,\dots,r\}

\text{.}</math>The [[Chinese remainder theorem]] guarantees there exists a unique solution <math>x\in\{0,\dots,n-1\}</math>.

:# Return <math>x</math>.

The correctness of this algorithm can be verified via the [[Abelian group#Classification|classification of finite abelian groups]]: Raising <math>g</math> and <math>h</math> to the power of <math>n/p_i^{e_i}</math> can be understood as the projection to the factor group of order <math>p_i^{e_i}</math>.

Line 46:

==References==

*{{cite book|title=An Introduction To Cryptography|url=https://archive.org/details/An_Introduction_to_Cryptography_Second_Edition|last=Mollin|first= Richard|date=2006-09-18|publisher=Chapman and Hall/CRC|edition=2nd|isbn=978-1-58488-618-1|page=[https://archive.org/details/An_Introduction_to_Cryptography_Second_Edition/page/n353 344]|ref=Mollin06}}

*{{cite journal |author1first1=S. |last1=Pohlig |author2-link=[[Martin Hellman|first2=M. |last2=Hellman]] | title=An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance | journal=IEEE Transactions on Information Theory | issue=24 | year=1978 | pages=106–110 | doi=10.1109/TIT.1978.1055817 | url=http://www-ee.stanford.edu/~hellman/publications/28.pdf}}

*{{cite book|first1=Alfred J.|last1=Menezes|author-link1=Alfred Menezes|first2=Paul C.|last2=van Oorschot|author-link2=Paul van Oorschot|first3=Scott A.|last3=Vanstone|author-link3=Scott Vanstone|title=Handbook of Applied Cryptography|url=https://archive.org/details/handbookofapplie0000mene/page/107|publisher=[[CRC Press]]|year=1997|pages=[https://archive.org/details/handbookofapplie0000mene/page/107 107–109]|chapter=Number-Theoretic Reference Problems|chapter-url=http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf|isbn=0-8493-8523-7|ref=Menezes97|url-access=registration}}