Faugere의 F4와 F5 알고리즘

컴퓨터 대수학에서, 장 샤를 포에르가 쓴 Faugere F4 알고리즘은 다변량 다항식 링의 이상에 대한 그뢰브너 기초를 계산한다.알고리즘은 Buchberger 알고리즘과 동일한 수학적 원리를 사용하지만, 일반적으로 희박한 행렬을 형성하고 빠른 선형대수를 사용하여 병렬로 축소를 수행함으로써 많은 정상적인 형태를 한 번에 계산한다.

Faugere F5 알고리즘은 우선 이상적인 발전기 다항식 쌍의 그뢰브너 기초를 계산한다.그런 다음 이 기준을 사용하여 발전기 초기 행렬의 크기를 다음 더 큰 기준으로 축소한다.

G가_prev 이미 계산된 그뢰브너 기초(f₂, …, f_m)이고 우리는 (f₁) + G의_prev 그뢰브너 기초(Gröbner basis)를 계산하고 싶다면, m은 G 요소의 선행_prev 용어로 구분할 수 없는 단수(m f)인₁ 행렬을 구성할 것이다.

이 전략은 Faugére가 다항식 서명이라고 부르는 것에 기초하여 알고리즘이 두 가지 새로운 기준을 적용할 수 있게 한다.이러한 기준들 덕분에, 알고리즘은 Gröbner 기반을 계산하는 알고리즘에서 가장 시간이 많이 소요되는 작업인 단일 다항식을 0으로 단순화하지 않고 정규 시퀀스라고 불리는 많은 종류의 흥미로운 다항식 시스템의 Gröbner 기반을 계산할 수 있다.또한 많은 수의 비정규 시퀀스에도 매우 효과적이다.

구현

Faugere F4 알고리즘이 구현됨

• FGb에서는, C/C++ 또는 Maple에서 그것을 사용하기 위한 인터페이스를 포함하는 Faugere의 자체 구현,
• 메이플 컴퓨터 대수 시스템에서는 옵션 방법=그루브너[gbasis] 함수의 fgb.
• 마그마 컴퓨터 대수 체계에서
• SageMath 컴퓨터 대수 체계에서,

Faugere F5 알고리즘의^{[citation needed]} 연구 버전은

• IMT-2000 3GPP-ULTE 컴퓨터 대수 시스템;^[1]
• SageMath 컴퓨터 대수 체계
• SymPy Python 패키지로.^[2]

적용들

이전에 다루기 어려웠던 "순환 10" 문제는,^{[citation needed]} 예를 들어 HFE와 C와^* 같은 암호학과 관련된 다수의 시스템과 마찬가지로 F5에 의해 해결되었다.^{[citation needed]}

참조

• Faugère, J.-C. (June 1999). "A new efficient algorithm for computing Gröbner bases (F₄)" (PDF). Journal of Pure and Applied Algebra. 139 (1): 61–88. doi:10.1016/S0022-4049(99)00005-5. ISSN 0022-4049.
• Faugère, J.-C. (July 2002). A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅) (PDF). Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC). ACM Press. pp. 75–83. CiteSeerX 10.1.1.188.651. doi:10.1145/780506.780516. ISBN 978-1-58113-484-1. S2CID 15833106.
• Stegers Faugere의 F5 알고리즘이 재방문될 때까지(대체 링크).2005년 9월 (2007년 4월 27일 개정) 졸업장-마테마티커 논문, 요하네스 부흐만 테크니쉬 유니버설스튜어드 달슈타트 고문.사용 가능한 구현에 대한 링크를 포함한 많은 참조 자료.

외부 링크

• Faugere의 홈 페이지(추가 문서의 PDF 재인쇄 포함)
• F4 알고리즘에 대한 소개.