대수군 인자화 알고리즘

Algebraic-group factorisation algorithm

대수-그룹 인자화 알고리즘은 그룹 구조가 '감소된 그룹'의 직접적인 합인2 대수 그룹 정의 모듈로 N에서 작업하여 정수 N을 인수하기 위한 알고리즘으로, 그룹 산술모듈로를 정의한1 방정식을 수행함으로써 얻어진다.중국의 나머지 정리에 의해 산술모듈로 N은 모든 감소된 그룹에서 동시에 산술에 해당한다.

목적은 그룹 모듈로 N의 정체성이 아닌 신원 모듈로 이루어진 요소를 찾는 것이므로 이러한 일방적 정체성을 인식할 수 있는 방법이 필요하다.일반적으로 요소를 이동시키고 감원된 그룹의 ID를 변경하지 않고 그대로 두는 작업을 수행함으로써 이들을 발견하게 된다.알고리즘이 단측 아이덴티티를 찾으면 향후 모든 용어 또한 단측 아이덴티티가 될 것이므로 주기적으로 점검하면 충분하다.

그룹 모듈로 N의 임의 요소 x를 선택하고 그 중 크고 부드러운 복수 Ax를 계산하여 계산한다. 하나 이상의 축소된 그룹 순서가 A의 구분자일 경우, 이는 인자를 산출한다.소자가 감소된 그룹 중 하나 이상에서 정체성이 될 수 있기 때문에 주요 요인이 될 필요는 없다.

일반적으로 A는 일부 제한 K 이하의 소수 산물로 간주되며, Ax는 이러한 소수 단위로 x의 연속 곱셈을 통해 계산된다. 각 곱셈, 또는 몇 곱하기마다 단측 아이덴티티를 위해 검사가 이루어진다.

2단계 절차

일반적으로 차이에 기초한 방법에 의해 그룹 요소에 제품보다 몇 개의 작은 정수를 더 빨리 곱하는 것이 종종 가능하다; 연속적인 소수점 사이의 차이를 계산하고 로 연속적으로 더한다이것은 2단계 절차가 합리적이라는 것을 의미한다. 먼저 x에 한계 B1 이하 모든 소수점을 곱한 다음, B1과 더 큰 한계 B2 사이의 모든 소수점에 대해 p Ax를 조사한다.

특정 대수집단에 해당하는 방법

대수집단이 승수군모드 N이라면 N과 함께 가장 큰 공통분위수를 계산하여 단측 정체성을 인식하며 그 결과는 p - 1 방법이다. 1 방법이다.

대수군이 N의 2차 확장의 승수군일 경우 결과는 p + 1 방법이며, 계산은 숫자 modulo N 쌍을 포함한다.Z/ Z[ 이가) 실제로 Z / N {\의 2차 확장인지 알 수 없다.이를 위해서는 t가 2차 잔류물 모듈로 N인지 알아야 하며, 인자를 알지 못한 상태에서 이를 수행하는 알려진 방법은 없다.단, N이 매우 많은 인자를 가지고 있지 않다면, 다른 방법을 먼저 사용해야 하는 경우, 무작위 t(또는 오히려2 t = A - 4)를 선택하는 것이 우연히 2차 비-재분율에 상당히 빨리 부딪히게 된다.t가 2차 잔류물일 경우 p+1 방법은 p - 1 방법의 느린 형태로 변한다.

대수군이 타원형 곡선인 경우 타원형 곡선 포인트 추가 절차에서 반전 실패에 의해 단측 아이덴티티를 인식할 수 있으며, 결과는 타원형 곡선법이다. Hasse의 정리에서는 타원형 곡선모듈로 p의 점수는 항상 2에 있다고 기술하고 있다..

위의 세 가지 대수적 그룹은 모두 GMP-ECM 패키지에 의해 사용되는데, 여기에는 2단계 절차의 효율적인 구현과 표준 이항 지수 접근법보다 다소 효율적인 PRAC 그룹-배수 알고리즘의 구현이 포함된다.

다른 대수적 그룹(N의 고차 확장 또는 상위 속들의 대수적 곡선에 해당하는 그룹)의 사용은 때때로 제안되지만 거의 항상 비현실적이다.이러한 방법은 p의 순서에 비해 순도가 훨씬 낮은 일부 d > 1의 경우 p의d 순서에 대한 순서에 대한 순도 제약을 받게 된다.