사이클 검출

Cycle detection
이 글은 반복되는 함수에 대한 것입니다.다른 용도는 사이클 검출(그래프 이론)을 참조하십시오.

컴퓨터 과학에서 주기 검출 또는 주기 소견은 반복되는 함수 값의 순서에서 주기를 찾는 알고리즘 문제입니다.

유한 집합 S를 그 자체에 매핑하는 함수 f 및 S의 모든 초기 값0 x에 대해 반복 함수 값의 시퀀스는

는 결국 같은 값을 두 번 사용해야 합니다.xj = x 가 되는i 몇 개의 구별되는 인덱스 i 와 j 가 존재해야 합니다.이러한 경우, x 에서i x 로 같은 일련의j − 1 값을 반복함으로써 시퀀스가 정기적으로 계속되어야 합니다.사이클 검출은 f 와0 x 로 주어진 i 와 j 를 찾는 문제입니다.

메모리를 거의 사용하지 않고 신속하게 사이클을 찾기 위한 몇 가지 알고리즘이 알려져 있습니다.로버트 W. 플로이드의 거북이와 토끼 알고리즘은 두 포인터가 동일한 값을 가리킬 때까지 값의 시퀀스를 통해 서로 다른 속도로 이동합니다.또는 브렌트의 알고리즘은 지수 검색의 개념을 기반으로 합니다.Floyd's 알고리즘과 Brent's 알고리즘은 모두 일정한 수의 메모리 셀만을 사용하며, 시퀀스의 시작부터 첫 번째 반복까지의 거리에 비례하는 많은 함수 평가를 받습니다.다른 몇 가지 알고리즘은 더 적은 함수 평가를 위해 더 많은 양의 메모리를 교환합니다.

사이클 검출의 적용은 의사난수 발생기와 암호 해시 함수의 품질 테스트, 계산수 이론 알고리즘, 컴퓨터 프로그램의 무한 루프 검출 및 셀룰러 오토마타의 주기적 구성, 링크드 리스트 데이터 구조의 자동 형상 분석 및 데드 검출을 포함한다.DBMS에서 트랜잭션 관리를 위한 잠금.

예

집합 {0,1,2,3,4,5,6,7,8}에서 오가는 함수 및 해당 함수 그래프

그림에는 집합 S = {0,1,2,3,4,5,6,7,8}을(를) 매핑하는 함수 f가 나와 있습니다.x = 2에서0 시작하여 f를 반복적으로 적용하면 값의 시퀀스가 표시됩니다.

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....

이 값 시퀀스의 사이클은 6, 3, 1입니다.

정의들

S를 유한 집합, f를 S에서 그 자신까지의 함수, x를0 S의 임의의 원소라고 하자.i > 0 의 경우는, x = f(xi − 1) 로 합니다i.값μ x가 값 x의 시퀀스 내에서i 무한히 자주 다시 나타나도록 μ를 가장 작은 지표로 하고, μ(루프 길이)를 xλ + μ = x와μ 같이 가장 작은 양의 정수라고 하자.사이클 검출 문제는 θ와 [1]μ를 찾는 작업이다.

그림에서와 같이 꼭지점이 S의 요소인 함수 그래프(즉, 각 정점이 단일 발신 에지를 갖는 유향 그래프)와 요소를 대응하는 함수 값에 매핑하는 에지를 구성함으로써 동일한 문제를 그래프 이론적으로 볼 수 있다.시작 정점0 x에서 도달 가능한 정점 집합은 그리스 문자 rho(θ)와 유사한 형상을 가진 서브그래프를 형성한다: x에서 [2]θ0 정점의 사이클까지의 길이 μ의 경로.

컴퓨터 표현

일반적으로 f는 위의 그림처럼 값의 테이블로 지정되지 않습니다.오히려 주기검출알고리즘은 값 x의i 시퀀스 또는 f를 계산하기 위한 서브루틴 중 하나에 접근해도 된다.이 작업은 시퀀스 값을 가능한 한 적게 조사하거나 서브루틴콜을 가능한 한 적게 실행하면서' 및 μ를 찾는 것입니다.또한 일반적으로 사이클 검출 문제에 대한 알고리즘의 공간 복잡성도 중요합니다.전체 시퀀스를 저장하는 데 필요한 메모리보다 훨씬 적은 양의 메모리를 사용하여 문제를 해결하려고 합니다.

일부 응용 프로그램, 특히 정수 인수분해를 위한 Pollard의 rho 알고리즘에서는 알고리즘이 S와 f에 훨씬 더 제한적으로 접근합니다.예를 들어 Pollard의 rho 알고리즘에서 S는 인수분해되는 숫자의 알 수 없는 소수인 정수모듈로의 집합이기 때문에 S의 크기조차 알고리즘에서 알 수 없다.이러한 제한된 지식으로 사이클 검출 알고리즘을 사용할 수 있도록 하기 위해 다음과 같은 기능을 기반으로 설계할 수 있습니다.처음에 알고리즘은 그 메모리 내에 시작값0 x에 대한 포인터를 나타내는 오브젝트가 있다고 가정한다.어느 단계에서나, 3가지 액션 중 하나를 실행할 수 있다.메모리 내의 다른 오브젝트에 포인터를 카피할 수도 있고, 시퀀스 내의 다음 오브젝트에 포인터를 적용하여 포인터를 대체할 수도 있다.또는 그 포인터 중 2개가 시퀀스 내의 동일한 값을 나타내는지 여부를 판단하기 위한 서브루틴을 적용할 수도 있다.동등성 테스트 동작은 중요하지 않은 계산을 수반할 수 있습니다.예를 들어, Pollard의 rho 알고리즘에서는 두 개의 저장된 값의 차이가 [2]인수분해되는 숫자의 중요하지 않은 최대공약수를 가지고 있는지 여부를 테스트함으로써 구현됩니다.이러한 맥락에서 계산의 포인터 머신 모델과 유사하게 포인터 복사, 시퀀스 내 진행 및 동등성 테스트만을 사용하는 알고리즘을 포인터 알고리즘이라고 할 수 있다.

알고리즘

f를 산출하기 위한 서브루틴으로서 입력이 주어지면, 단순히 값i x의 시퀀스를 계산하고 해시 테이블 등의 데이터 구조를 사용하여 이들 값을 기억하여 각 후속 값이 이미 기억되어 있는지 여부를 테스트하는 것만으로 사이클 검출 문제를 해결할 수 있다.단, 이 알고리즘의 공간 복잡도는 불필요하게 큰 θ + μ에 비례합니다.또한 이 방법을 포인터 알고리즘으로 구현하려면 각 값 쌍에 동등성 테스트를 적용해야 하므로 전체적으로 2차 시간이 발생합니다.따라서 이 영역의 연구는 두 가지 목표에 집중되어 왔다. 즉, 이 순진한 알고리즘보다 적은 공간을 사용하는 것과 동등성 테스트를 사용하는 포인터 알고리즘을 찾는 것이다.

플로이드의 거북이와 토끼

순서 2, 0, 6, 3, 1, 6, 1, 6, 1, ...에 적용되는 Floyd의 "Tortoise and hare" 사이클 검출 알고리즘.

Floyd의 사이클 검색 알고리즘은 두 개의 포인터만 사용하는 포인터 알고리즘으로, 서로 다른 속도로 시퀀스를 이동합니다.이것은 또한 이솝 우화인 거북이와 토끼를 암시하는 "토르토이즈와 토끼 알고리즘"이라고도 불린다.

이 알고리즘의 이름은 Robert W의 이름을 따서 붙여졌습니다. 도날드 [3][4]크누스에 의해 발명된 플로이드.그러나 이 알고리즘은 Floyd의 출판물에는 나타나지 않으며 이는 잘못된 속성일 수 있습니다.Floyd는 1967년 [5]논문에서 모든 단순한 사이클을 유향 그래프로 나열하는 알고리즘을 설명하지만, 이 문서의 주제인 기능 그래프의 사이클 검색 문제는 설명하지 않습니다.사실, 인용 없이 플로이드의 것이라고 한 크누스의 진술(1969년)은 인쇄물로는 처음으로 알려진 것이고, 따라서 그것은 개인에 [6]의한 것이 아니라 민속 정리일 수도 있다.

알고리즘의 주요 통찰력은 다음과 같습니다.사이클이 있는 경우, 임의의 정수 i μμ 및 k 00, xi=x에i + kλ 대해 θ는 찾는 루프의 길이이고, μ는 사이클의 제1원소의 지수이며, k는 루프수를 나타내는 정수이다.이를 바탕으로 x = x일 경우에만2i i = k≤ μ라는 것을 알 수 있다(사이클에서 x2i = x일 경우ii, i = i + k ,, i = k ;, i = k = k = x = x = i + k , 등 i와 k가 존재한다면 i = k = k = ki + kλ 및 x2i = x)따라서 알고리즘은 이 특수한 형식의 반복값을 체크하기만 하면 됩니다.이 값은 시퀀스 시작에서 다른 값의 2배만큼 떨어져 있기 때문에 반복 주기 θ가 θ의 배수입니다.일단 ν 발견되면, 알고리즘은 처음부터 순서의 첫번째 반복 값 xμ을 찾기가 사실λ가 분열되 ν고 따라서를 사용하여 시퀀슸던은 xμ)xμ+v마지막으로 한번, 값의 μ 것으로 알려져 그것은 사소한 누군가를 길이 λ의 가장 짧은 반복 주기에 의해 검색을 위해서 맨 처음 위치 μ+λ에 xμ+λ.)xμ.

따라서 알고리즘은 주어진 시퀀스에 대한 2개의 포인터를 유지합니다.하나는 x에서i, 다른 하나는 x에서입니다2i.알고리즘의 각 단계에서 i가 1씩 증가하여 거북이는 1단계 전진하고 토끼는 2단계 전진하여 이들 2가지 포인터의 시퀀스 값을 비교한다.거북이와 토끼가 같은 값을 가리키는 i >0의 최소값은 원하는 값이다.

다음 Python 코드는 이 아이디어가 알고리즘으로 구현되는 방법을 보여줍니다. 

방어하다 플로이드(f, x0):     # 알고리즘의 주요 단계: 반복 x_i = x_2i를 구한다.     # 토끼는 거북이보다 두 배나 빨리 움직이고     # 스텝마다 1씩 거리가 늘어납니다.     # 결국 둘 다 사이클 안에 들어가게 되고     # 어느 순간 그들 사이의 거리는     # 마침표 λ로 나누어진다.     거북이 = f(x0) # f(x0)는 x0 옆에 있는 요소 또는 노드입니다.     토끼 = f(f(x0))     하는 동안에 거북이 != 토끼:         거북이 = f(거북이)         토끼 = f(f(토끼))        # 이 시점에서 거북의 위치 ,도 같음     # 산토끼와 거북이의 거리까지로 나누면     # 마침표 λ.산토끼는 한 번에 한 발씩 원을 그리며 움직이며     #와 거북이(x0)는 원을 향해 움직인다.     #는 원의 시작 부분에서 교차합니다.왜냐하면     둘 사이의 거리는 ,의 배수인 2µ로 일정합니다.     # 거북이가 지수 μ에 도달하면 그들은 동의할 것이다.      # 첫 번째 반복 위치 μ를 구한다.         뮤 = 0     거북이 = x0     하는 동안에 거북이 != 토끼:         거북이 = f(거북이)         토끼 = f(토끼)   # 토끼와 거북이는 같은 속도로 움직인다         뮤 += 1       # x_μ부터 최단주기의 길이를 구한다.     # 거북이가 가만히 있을 때 산토끼는 한 발짝씩 움직인다.     # lam은 is가 발견될 때까지 증가합니다.     램 = 1     토끼 = f(거북이)     하는 동안에 거북이 != 토끼:         토끼 = f(토끼)         램 += 1       돌아가다 램, 뮤

이 코드는 포인터, 함수 평가 및 동등성 테스트를 저장 및 복사하는 방식으로만 시퀀스에 액세스하므로 포인터 알고리즘으로 인정됩니다.알고리즘에서는, 이러한 타입의 O(θ + μ) 연산과 O(1) 스토리지 [7]스페이스를 사용합니다.

브렌트 알고리즘

리처드 P. 브렌트는 거북이 및 토끼 알고리즘과 마찬가지로 [8]시퀀스에 두 개의 포인터만 있으면 되는 대체 사이클 검출 알고리즘을 설명했습니다.다만, 이것은 다른 원리에 근거하고 있습니다.즉, 2의i 최소제곱이 θ와 μ보다 큰 것을 검색합니다.i = 0, 1, 2, ...의 경우, 알고리즘은 x를 2의 다음 거듭제곱까지 이후의 각 시퀀스 값과2i−1 비교하며, 일치하는 값을 찾으면 중지합니다.거북이 및 토끼 알고리즘과 비교하여 두 가지 장점이 있다. 즉, 후속 단계에서 검색할 필요 없이 사이클의 정확한 길이 θ를 직접 찾고, 그 단계는 [9]3이 아닌 f에 대한 한 번의 평가만 수반한다.

다음 Python 코드는 이 기술이 어떻게 작동하는지 자세히 보여줍니다. 

방어하다 브렌트(f, x0):     # 메인 단계: 2의 연속 파워 검색     힘 = 램 = 1     거북이 = x0     토끼 = f(x0)  # f(x0)는 x0 옆에 있는 요소 또는 노드입니다.     하는 동안에 거북이 != 토끼:         한다면 힘 == 램:  # 2의 새로운 힘을 시작할 시간이야?             거북이 = 토끼             힘 *= 2             램 = 0         토끼 = f(토끼)         램 += 1      # 길이의 첫 번째 반복 위치 찾기 »     거북이 = 토끼 = x0     위해서 i 에 범위(램):     # range(lam)는 값이 0, 1, ..., lam-1인 목록을 생성합니다.         토끼 = f(토끼)     # 산토끼와 거북이의 거리는 λ입니다.      # 다음, 토끼와 거북이는 그들이 동의할 때까지 같은 속도로 움직인다.     뮤 = 0     하는 동안에 거북이 != 토끼:         거북이 = f(거북이)         토끼 = f(토끼)         뮤 += 1       돌아가다 램, 뮤

거북이 및 토끼 알고리즘과 마찬가지로 O(θ + μ) 테스트 및 함수 평가와 O(1) 스토리지 공간을 사용하는 포인터 알고리즘입니다.함수 평가 횟수가 플로이드의 알고리즘보다 결코 많을 수 없다는 것을 보여주는 것은 어렵지 않습니다.Brent는 자신의 사이클 검색 알고리즘이 Floyd보다 평균적으로 약 36% 더 빠르게 실행되며 Pollard rho 알고리즘의 속도가 약 24% 더 빨라진다고 주장했습니다.그는 또한 알고리즘의 무작위 버전에 대한 평균 사례 분석을 수행하는데, 여기서 두 포인터 중 느린 포인터에 의해 추적되는 지수의 시퀀스는 두 포인터의 거듭제곱이 아니라 두 포인터의 거듭제곱의 무작위 배수이다.그의 주요 용도는 정수 인수분해 알고리즘이었지만, 브렌트는 의사 난수 [8]생성기 테스트에서의 응용에 대해서도 논의했다.

고스퍼 알고리즘

R. W. Gosper 알고리즘은[10][11] 첫 번째 사이클의 시작점 l \ style \ _ { } u \ \ _ {}의 기간{\\ displaystyle \ _ { u 를 구합니다.하한과 상한의 차이는 주기와 같은 순서입니다( l + ~h { style \ _ { + \ \ _ { }） 。

Gosper 알고리즘의 주요 특징은 발전기 함수를 재평가하기 위해 백업하지 않고 공간과 시간 모두에서 경제적이라는 것입니다.그것은 대략 브렌트 알고리즘의 병렬 버전이라고 할 수 있다.브렌트 알고리즘은 거북이와 토끼 사이의 간격을 점차 늘리는 반면, 고스퍼 알고리즘은 대략 기하급수적으로 간격을 두고 있는 여러 거북이를 사용한다.HACMEM 항목 132의 주기에 따르면, 이 알고리즘은 예를 들어 사이클이 최대 2회 반복되는 세 번째 값이 발생하기 전에 반복을 검출한다. 이 메모에서는 이전 값 ( "")\ ( \ \ lambda previous previous previous[10];;;;;;;;;;;;;;;; this;; （ +" ) \ \ Theta \ )） values values values values values values this this values values this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this this예를 들어 함수 값은 32비트 정수이며 사이클의 두 번째 반복은 시작 이후 최대32 2개의 함수 평가 후에 종료되는 것으로 알려져 있습니다.+ 2 { \+ 2 \ 2{ 。그러면 33개의 32비트 정수를 저장할 수 있습니다.

함수의 i i를 평가할 때 알고리즘은 생성된 을 Oi의 이전 값과 비교합니다.i i가 μ +†(\ 및 μ + †(\ style + 까지 올라가는 을 확인합니다. 따라서 이 의 시간 복잡도는 O (( + )⋅ ( + O ( ( ( \ mu + \ )\ \ ( \ mu + \ }입니다 알고리즘은 ( log( ( + + ）\ \ ta \ ta \ style \ ta \ ta ( ) 。) ) 。이는 이 문서 전반에 걸쳐 함수 값의 크기가 일정하다는 일반적인 가정 하에 이루어집니다.이 전제 하에 공간의 복잡도는 2 ( + style (\+\)}} 입니다.는 최소 + ( \ \ + \ } )가 필요하기 때문에 각 값의 크기는 ( logdisplay + 입니다

시공간 트레이드오프

많은 저자들이 Floyd와 Brent의 방법보다 더 많은 메모리를 사용하지만 더 빨리 사이클을 검출하는 사이클 검출 기술을 연구했습니다.일반적으로 이러한 메서드는 이전에 계산된 여러 시퀀스 값을 저장하고 각 새 값이 이전에 계산된 값 중 하나인지 여부를 테스트합니다.이를 신속하게 수행하기 위해 이들은 일반적으로 해시 테이블 또는 유사한 데이터 구조를 사용하여 이전에 계산된 값을 저장합니다. 따라서 포인터 알고리즘이 아닙니다. 특히, 그것들은 일반적으로 Pollard의 rho 알고리즘에 적용할 수 없습니다.이러한 방법이 다른 점은 저장할 값을 결정하는 방법입니다.Nivasch에 [12]이어 이러한 기술에 대해 간략히 살펴봅니다.

  • 브렌트는 저장된 시퀀스 값의 지수가 2가 아닌 숫자 R의 거듭제곱인 그의 기술의 변형을 이미 기술하고 있다[8].사이클 검출 알고리즘은 R을 1에 가까운 수로 선택하고, 그 시퀀스 값을 R의 연속 거듭제곱의 배열에 가까운 인덱스에 격납함으로써 최적의 θ+[13][14]μ의 임의의 소인수 내에 있는 다수의 함수 평가를 이용할 수 있다.
  • Sedgewick, Szymanski 및[15] Yao는 M개의 메모리셀을 사용하여 최악의 경우에만 ( +)( + M - / )\ ( \ + \ ) ( + { - 1 / } )의 함수 평가를 필요로 하는 방법을 제공하고 있습니다.이러한 값은 최적이 됩니다.이 방법에는 숫자 파라미터 d를 유지하고, d의 배수인 시퀀스의 위치만 테이블에 저장하며, 너무 많은 값이 저장될 때마다 테이블을 지우고 d를 두 배로 늘리는 작업이 포함됩니다.
  • 몇몇 저자들은 (Sedgewick 등의 방법에서와 같이) 위치에 기초한 것이 아니라 값을 포함하는 기준에 기초하여 표에 함수 값을 저장하는 구별된 포인트 방법을 설명했다.예를 들어, 0 modulo 일부 값 d와 같은 값이 [16][17]저장될 수 있습니다.간단히 말하면, Nivasch는[12] D. P. Woodruff에 대해 이전에 본 값의 랜덤 표본을 저장하여 각 단계에서 표본을 랜덤으로 유지하도록 적절한 랜덤 선택을 하는 제안을 신뢰한다.
  • Nivasch는[12] 고정된 양의 메모리를 사용하지 않지만 (입력 함수가 랜덤이라고 가정할 때) 사용되는 예상 메모리 양이 시퀀스 길이에서 로그인 알고리즘을 나타냅니다.더 작은 값을 가진 최신 항목이 없을 때 이 기술을 사용하여 항목이 메모리 테이블에 저장됩니다.Nivasch에서 알 수 있듯이 이 기술을 사용하는 항목은 스택 데이터 구조를 사용하여 유지관리할 수 있으며, 연속되는 각 시퀀스 값은 스택의 상단과만 비교할 필요가 있습니다.최소값의 반복 시퀀스 요소가 발견되면 알고리즘이 종료됩니다.여러 스택에서 동일한 알고리즘을 실행하고 값의 랜덤한 순열을 사용하여 각 스택 내의 값을 정렬하면 이전 알고리즘과 유사한 시공간 트레이드오프가 가능합니다.단, 2개의 값 중 어느 쪽이 작은지 판단하기 위해 비교가 필요하기 때문에 단일 스택을 사용하는 이 알고리즘의 버전도 포인터 알고리즘이 아닙니다.

입력 시퀀스에서 최대 M 값을 저장하는 사이클 검출 알고리즘은 최소 ( +) ( + - )\ ( \ + \ ) \ left ( + { \ { \ )의 함수 [18][19]평가를 수행해야 합니다.

적용들

사이클 검출은 많은 어플리케이션에서 사용되고 있습니다.

  • 의사 난수 발생기의 사이클 길이를 결정하는 것은 그 강도의 한 가지 척도입니다.이것은 플로이드의 [3]방법을 설명할 때 Knuth가 인용한 응용 프로그램입니다.브렌트는[8] 이러한 방식으로 선형 합동 생성기를 테스트한 결과를 기술합니다. 그 기간은 광고된 것보다 훨씬 짧았습니다.보다 복잡한 발전기의 경우 사이클이 발견되는 값의 시퀀스는 발전기의 출력이 아니라 내부 상태를 나타낼 수 있습니다.
  • 정수 인수분해를[20] 위한 폴라드의 rho 알고리즘과 이산 로그 [21]문제를 위한 그의 관련 캥거루 알고리즘을 포함한 몇 가지 수 이론 알고리즘이 주기 검출에 기초하고 있다.
  • 암호화 어플리케이션에서는 같은 값 x에 대해 어떤 암호화 함수 to에 의해 매핑된2개의 다른 값μ−-1 x와λ+μ−-1μ x를 찾을 수 있는 것은 ƒ의 약점을 나타낼 수 있습니다.예를 들어 Quisquater와 Delescaiu는[17] 메시지 및 메시지를 동일한 암호화 값에 매핑하는 Data Encryption Standard 키 쌍 검색에 사이클 검출 알고리즘을 적용합니다.Kaliski, Rivest 및[22] Sherman도 사이클 검출 알고리즘을 사용하여 DES를 공격합니다.이 기술은 암호화 해시 [23]함수에서 충돌을 찾기 위해서도 사용할 수 있습니다.
  • 사이클 검출은 특정 유형의 컴퓨터 [24]프로그램에서 무한 루프를 검출하는 방법으로 도움이 될 수 있습니다.
  • 셀 오토마톤 시뮬레이션의 주기적 구성은 오토마톤 [12]상태의 시퀀스에 주기적 검출 알고리즘을 적용함으로써 찾을 수 있다.
  • 링크 리스트 데이터 구조의 형상 분석은 이러한 구조를 이용한 알고리즘의 정확성을 검증하는 기술이다.목록 내의 노드가 같은 목록의 이전 노드를 잘못 가리킬 경우 구조체는 [25]이러한 알고리즘으로 검출할 수 있는 사이클을 형성합니다.Common Lisp에서 S-Expression 프린터로 제어되는*print-circle*variable을 지정하면 순환 리스트 구조가 검출되어 컴팩트하게 인쇄됩니다.
  • 테스케는[14] 연산군 이론에서 응용을 설명한다: 생성자 집합에서 아벨 군의 구조를 결정하는 것이다.Kaliski [22]등의 암호화 알고리즘은 알려지지 않은 그룹의 구조를 추론하려는 시도라고 볼 수도 있다.
  • Fich(1981)는 William Kahan의 소행으로 여겨지는 천체역학의 컴퓨터 시뮬레이션에 대한 응용을 간략히 언급하고 있다.본 어플리케이션에서는 궤도계의 위상공간에서의 사이클 검출을 사용하여 [18]시스템이 시뮬레이션의 정확도 범위 내에서 주기적인지 여부를 판단할 수 있다.
  • Mandelbrot Set fractal(만델브로트 세트 프랙탈) 생성에서는 영상 생성 속도를 높이기 위해 일부 성능 기법이 사용됩니다.그 중 하나는 "주기 검사"라고 불리며, 점 궤도에서 주기를 찾는 것으로 구성됩니다.이 문서에서는 "주기 검사" 기법에 대해 설명합니다.여기서 또 다른 설명을 찾을 수 있습니다.이 기술을 구현하려면 몇 가지 사이클 검출 알고리즘을 구현해야 합니다.

레퍼런스

  1. ^ 를 클릭합니다Joux, Antoine (2009), Algorithmic Cryptanalysis, CRC Press, p. 223, ISBN 9781420070033.
  2. ^ a b Joux (2009년, 페이지 224).
  3. ^ a b Knuth, Donald E. (1969), The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, p. 7, exercises 6 and 7
  4. ^ 응용 암호 핸드북, Alfred J. Menezes, Paul C. van Oorschot, Scott A.Vanstone, 페이지 125는 이 알고리즘과 기타에 대해 설명합니다.
  5. ^ Floyd, R.W. (1967), "Nondeterministic Algorithms", J. ACM, 14 (4): 636–644, doi:10.1145/321420.321422, S2CID 1990464
  6. ^ The Hash Function BLAKE, Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen(2015), 페이지 21, 각주 8
  7. ^ Joux(2009), 섹션 7.1.1, Floyd의 주기 탐색 알고리즘, 페이지 225–226.
  8. ^ a b c d 를 클릭합니다Brent, R. P. (1980), "An improved Monte Carlo factorization algorithm" (PDF), BIT Numerical Mathematics , 20 (2): 176–184, doi:10.1007/BF01933190, S2CID 17181286.
  9. ^ Joux (2009), 섹션 7.1.2, 브렌트의 사이클 검색 알고리즘, 페이지 226–227.
  10. ^ a b "Archived copy". Archived from the original on 2016-04-14. Retrieved 2017-02-08.{{cite web}}: CS1 maint: 제목으로 아카이브된 복사(링크)
  11. ^ "Hakmem -- Flows and Iterated Functions -- Draft, Not Yet Proofed".
  12. ^ a b c d 를 클릭합니다Nivasch, Gabriel (2004), "Cycle detection using a stack", Information Processing Letters, 90 (3): 135–140, doi:10.1016/j.ipl.2004.01.016.
  13. ^ 를 클릭합니다Schnorr, Claus P.; Lenstra, Hendrik W. (1984), "A Monte Carlo factoring algorithm with linear storage", Mathematics of Computation, 43 (167): 289–311, doi:10.2307/2007414, hdl:1887/3815, JSTOR 2007414.
  14. ^ a b 를 클릭합니다Teske, Edlyn (1998), "A space-efficient algorithm for group structure computation", Mathematics of Computation, 67 (224): 1637–1663, Bibcode:1998MaCom..67.1637T, doi:10.1090/S0025-5718-98-00968-5.
  15. ^ 를 클릭합니다Sedgewick, Robert; Szymanski, Thomas G.; Yao, Andrew C.-C. (1982), "The complexity of finding cycles in periodic functions", SIAM Journal on Computing, 11 (2): 376–390, doi:10.1137/0211030.
  16. ^ 를 클릭합니다van Oorschot, Paul C.; Wiener, Michael J. (1999), "Parallel collision search with cryptanalytic applications", Journal of Cryptology, 12 (1): 1–28, doi:10.1007/PL00003816, S2CID 5091635.
  17. ^ a b 를 클릭합니다Quisquater, J.-J.; Delescaille, J.-P., "How easy is collision search? Application to DES", Advances in Cryptology – EUROCRYPT '89, Workshop on the Theory and Application of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 434, Springer-Verlag, pp. 429–434, doi:10.1007/3-540-46885-4_43.
  18. ^ a b 를 클릭합니다Fich, Faith Ellen (1981), "Lower bounds for the cycle detection problem", Proc. 13th ACM Symposium on Theory of Computing, pp. 96–105, doi:10.1145/800076.802462.
  19. ^ 를 클릭합니다Allender, Eric W.; Klawe, Maria M. (1985), "Improved lower bounds for the cycle detection problem", Theoretical Computer Science, 36 (2–3): 231–237, doi:10.1016/0304-3975(85)90044-1.
  20. ^ 를 클릭합니다Pollard, J. M. (1975), "A Monte Carlo method for factorization", BIT, 15 (3): 331–334, doi:10.1007/BF01933667, S2CID 122775546.
  21. ^ 를 클릭합니다Pollard, J. M. (1978), "Monte Carlo methods for index computation (mod p)", Mathematics of Computation, American Mathematical Society, 32 (143): 918–924, doi:10.2307/2006496, JSTOR 2006496.
  22. ^ a b 를 클릭합니다Kaliski, Burton S., Jr.; Rivest, Ronald L.; Sherman, Alan T. (1988), "Is the Data Encryption Standard a group? (Results of cycling experiments on DES)", Journal of Cryptology, 1 (1): 3–36, doi:10.1007/BF00206323, S2CID 17224075.
  23. ^ Joux(2009), 섹션 7.5, 해시함수 충돌, 페이지 242–245.
  24. ^ 를 클릭합니다Van Gelder, Allen (1987), "Efficient loop detection in Prolog using the tortoise-and-hare technique", Journal of Logic Programming, 4 (1): 23–31, doi:10.1016/0743-1066(87)90020-3.
  25. ^ 를 클릭합니다Auguston, Mikhail; Hon, Miu Har (1997), "Assertions for Dynamic Shape Analysis of List Data Structures", AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging, Linköping Electronic Articles in Computer and Information Science, Linköping University, pp. 37–42.

외부 링크