러시아 4인방 방법

컴퓨터 과학에서, Method of Four Russians는 Boolean 매트릭스를 포함하는 알고리즘, 또는 보다 일반적으로 각 셀이 가능한 값의 한정된 수만을 차지할 수 있는 매트릭스를 포함하는 알고리즘을 가속화하는 기술이다.

아이디어

메소드의 주요 아이디어는 일부 파라미터 t에 대해 매트릭스를 t × t 크기의 작은 사각형 블록으로 분할하고, 룩업 테이블을 사용하여 각 블록 내에서 알고리즘을 신속하게 수행하는 것이다.룩업 테이블의 인덱스는 알고리즘의 일부 작동 전에 블록 경계 왼쪽 상단의 매트릭스 셀 값을 인코딩하고, 룩업 테이블의 결과는 연산 후 블록 우측 하단의 경계 셀 값을 인코딩한다.따라서 전체 알고리즘은 매트릭스 셀이 아닌² (n/t)² 블록에서만 작동하여 수행할 수 있으며, 여기서 n은 매트릭스의 측면 길이다.조회 테이블의 크기(및 초기화에 필요한 시간)를 충분히 작게 유지하기 위해 t는 일반적으로 O(log n)로 선택된다.

적용들

네 명의 러시아인 방법을 적용할 수 있는 알고리즘은 다음과 같다.

• 그래프의 전이성 폐쇄를 계산한다.
• 부울 행렬 곱하기,
• 거리 계산 편집,
• 시퀀스 정렬,
• 이진 뒤섞인 패턴 일치를 위한 인덱스 계산.

이 경우 각각 하나 또는 두 개의 로그 인자에 의해 알고리즘의 속도를 높인다.

Bard가 발행한 Method of Four Russian matrix inversion 알고리즘은 M4RI 라이브러리에서 구현되며₂, M4RI를 통한 조밀한 산술은 SageMath와 PolyBoRi 라이브러리에서 사용된다.^[1]

역사

이 알고리즘은 V. L. 알라자로프, E. A. 다이닉, M. A. 크론로드, 그리고 I에 의해 도입되었다.1970년 A. 패러디예프.^[2]이름의 유래는 알 수 없다; 아호, 홉크로프트 & 울만(1974)은 다음과 같이 설명한다.

발명가의 카디널리티와 국적 뒤에 흔히 '4러시아인' 알고리즘으로 불리는 두 번째 방법은 정리 6.9의 알고리즘보다 다소 '실용적'이다.^[3]

네 명의 작가 모두 당시 러시아 모스크바에서 일했다.^[4]

메모들

참조

• Arlazarov, V.; Dinic, E.; Kronrod, M.; Faradžev, I. (1970), "On economical construction of the transitive closure of a directed graph", Dokl. Akad. Nauk SSSR, 194 (11). Original title: "Об экономном построении транзитивного замыкания ориентированного графа", published in Доклады Академии Наук СССР134 (3), 1970.
• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), The design and analysis of computer algorithms, Addison-Wesley
• Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, ISBN 978-0-387-88756-2