로그에 대한 폴라드의 rho 알고리즘

폴라드의 로그 rho 알고리즘은 존 폴라드가 1978년 이산 로그 문제를 해결하기 위해 도입한 알고리즘으로, 폴라드의 정수 인자화 문제 해결을 위한 rho 알고리즘과 유사하다.

The goal is to compute ${\displaystyle \gamma }$ such that ${\displaystyle \alpha ^{\gamma }=\beta }$, where ${\displaystyle \beta }$ belongs to a cyclic group ${\displaystyle G}$ generated by ${\displaystyle \alpha }$. The algorithm computes integers ${\displaystyle a}$, ${\displayst$$yle b}$, ${\displaystyle A}$, and ${\displaystyle B}$ such that ${\displaystyle \alpha ^{a}\beta ^{b}=\alpha ^{A}\beta ^{B}}$. If the underlying group is cyclic of order ${\displaystyle n}$, by substituting ${\displaystyle \beta }$ as ${\displaystyle a^{\gamma }}$$$ 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 ${\displaystyle n}$, we get that ${\displaystyle \gamma }$ is one of the solutions of the equation ${\displaystyle (B-b)\gamma =(a-A){\pmod {n}}}$. Solutions는 확장된 유클리드 알고리즘을 사용하여 쉽게 얻을 수 있다.

To find the needed ${\displaystyle a}$, ${\displaystyle b}$, ${\displaystyle A}$, and ${\displaystyle B}$ the algorithm uses Floyd's cycle-finding algorithm to find a cycle in the sequence ${\displaystyle x_{i}=\alpha ^{a_{i}}\beta ^{b_{i}}}$, where the function ${\displaystyle f:x_{}}$${\displaystyle f:x_{i}\mapsto x_{i+1}}$ is assumed to be random-looking and thus is likely to enter into a loop of approximate length ${\displaystyle {\sqrt {\frac {\pi n}{8}}}}$ after ${\displaystyle {\sqrt {\frac {\pi n}{8}}}}$ steps.이러한 함수를 정의하는 한 가지 방법은 다음과 같은 규칙을 사용하는 것이다.$G{\displaystyle }$ ${\displaystyle G}$을(를) 대략 같은 크기의 세 개의 분리 하위 집합으로 나누십시오.${\displaystyle S_{0}}$, ${\displaystyle S_{1}}$, and ${\displaystyle S_{2}}$. If ${\displaystyle x_{i}}$ is in ${\displaystyle S_{0}}$ then double both ${\displaystyle a}$ and ${\displaystyle b}$; if ${\displaystyle x_{i}\in S_{1}}$ then$x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {S\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\$}}인 경우 ${\displaystyle$ $a}$을(를$)$ 증분하고 b {\displaystyle $b}$을(를) 증분한다$.$

알고리즘.

Let ${\displaystyle G}$ be a cyclic group of order ${\displaystyle p}$, and given ${\displaystyle \alpha ,\beta \in G}$, and a partition ${\displaystyle G=S_{0}\cup S_{1}\cup S_{2}}$, let ${\displaystyle f:$$G\to G}$이(가) 지도임

${\displaystyle f(x)={\begin{case}\beta x&x\in S_{0}\\\x^{2}\\nalpha x&x\in S_{2}\end{case}}}}}}}}$

지도 $g{\displaystyle }$: ${\displaystyle G}$ ${\displaystyle \times }$ ${\displaystyle Z\mathbb{}}$→ ${\displaystyle Z\mathbb{}}$ ${\$ g$:$${\displaystyle G}$$\time \mathb$ {$Z} \to \mathb${$Z}$ 및 h${\displaystyle }$: ${\displaystyle G\mathbb{}}$ ${\displaystyle \times }$ Z${\displaystyle }$→ Z ${\$$G\time \mathb {Z} \to \mathb {$Z$}$ } ~ \mathb {Z$$$}$ }

${\displaystyle {\begin{aligned}g(x,n)&={\begin{cases}n&x\in S_{0}\\2n{\pmod {p}}&x\in S_{1}\\n+1{\pmod {p}}&x\in S_{2}\end{cases}}\\h(x,n)&={\begin{cases}n+1{\pmod {p}}&x\in S_{0}\\2n{\pmod {p}}&x\in S_{1}\\n&x\in S_{2}\end{cases}}\end{aligned}}}$

입력: a: G b의 생성기: G 출력의 요소:정수 등이 도끼)b, 또는 실패 Initialise a0 ← 0,b0 ← 0,x0 ← 1∈ G나는 ← 1루프 크시 ← f(xi-1),← g(xi-1, ai-1), bi ← h(xi-1, bi-1)x2i ← f(f(x2i-2)),a2i ← g(f(x2i-2), g(x2i-2,a2i-2)),b2i ← h(f(x2i-2), h(x2i-2,b2i-2)한 경우-자이)x2i 다음 r ← bi-b2i 만약 r0복귀 실패=)← r−1(a2i-짓)모드 와 돌아옵니다. X 다른//크시 ≠ 끝나면 루프 나는 나는 + 1끝 ← x2i.

예

예를 들어 2 modulo N =${\displaystyle 1019}$ ${\displaystyle$ N$=1019}$에 의해 생성된 그룹을 고려하십시오($$ 그룹의 순서는 $n{\displaystyle }$= ${\displaystyle 1018}$ ${\displaystyle n=1018$ 2는 modulo 1019 단위 그룹을 생성함).알고리즘은 다음 C++ 프로그램에 의해 구현된다.

#include <stdio.h>  경솔하게 굴다 인트로 n = 1018, N = n + 1;  /* N = 1019 -- 프라임 */ 경솔하게 굴다 인트로 알파의 = 2;            /* 생성기 */ 경솔하게 굴다 인트로 베타. = 5;             /* 2^{10} = 1024 = 5 (N) */  공허하게 하다 new_xab(인트로& x, 인트로& a, 인트로& b) {   바꾸다 (x % 3) {   케이스 0: x = x * x     % N;  a =  a*2  % n;  b =  b*2  % n;  부숴뜨리다;   케이스 1: x = x * 알파의 % N;  a = (a+1) % n;                  부숴뜨리다;   케이스 2: x = x * 베타.  % N;                  b = (b+1) % n;  부숴뜨리다;   } }  인트로 본래의(공허하게 하다) {   인트로 x = 1, a = 0, b = 0;   인트로 X = x, A = a, B = b;   을 위해 (인트로 i = 1; i < n; ++i) {     new_xab(x, a, b);     new_xab(X, A, B);     new_xab(X, A, B);     활자화하다("%3d %4d %3d %3d %4d %3d %3d\n", i, x, a, b, X, A, B);     만일 (x == X) 부숴뜨리다;   }   돌아오다 0; } 

결과는 다음과 같다(편집).

i x a b X A B ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1000 3 0 0 0 0 0 0 0 3 4 1000 3 0 0 0 3680 376    86 299 412 49   101 680 377   860 300 413 50   505 680 378   101 300 415 51  1010 681 378  1010 301 416

That is ${\displaystyle 2^{681}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}}$ and so ${\displaystyle (416-378)\gamma =681-301{\pmod {1018}}}$, for which ${\displaystyle \gamma _{1}=10}$ is a solution as expected. $n{\displaystyle }$= ${\displaystyle 1018}$ ${\displaystyle n=1018}$이(가) 프라임이 아니므로, 2 ${\displaystyle {519}^{}}$= ${\displaystyle 1014}$=${\displaystyle }$- ${\displaystyle 5(\mathrm{모드}}$ $){\$이$($가) 보류되는 다른 ${\displaystyle {솔루션}_{}}$도 있다$.$

복잡성

실행 시간은 ${\displaystyle 대략\sqrt{}}$ $O{\displaystyle \mathcal{}}$( n${\displaystyle }$) ${\displaystyle {\mathcal{O}({\sqrt{n})}.$Pohlig–과 함께 사용하는 경우Hellman 알고리즘, 결합된 알고리즘의 실행 시간은 $O{\displaystyle \mathcal{}}$( ${\displaystyle p}$) ${\displaystyle {\mathcal {O}({\sqrt{p})}$이며$,$ 여기서 $p{\displaystyle }$ ${\displaystyle p}$은 $n{\displaystyle }$ ${\displaystyle n}$의 가장 큰 주요 요인이다$.$

참조

• Pollard, J. M. (1978). "Monte Carlo methods for index computation (mod p)". Mathematics of Computation. 32 (143): 918–924. doi:10.2307/2006496.
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (2001). "Chapter 3" (PDF). Handbook of Applied Cryptography.