격자 체이빙

격자체 체이빙은 넓은 지역에 걸쳐$$ 이바리테이트 $다항식{\displaystyle }$ f${\displaystyle (,a}$ , ${\displaystyle b}$) ${\디스플레이$ 스타일 $f(a,b)}$의 부드러운 값을 찾는 기법이다.그것은 거의 독점적으로 숫자 필드 체와 함께 사용된다.격자 체에 대한 원래 생각은 존 폴라드에서 나왔다.^[1]

The algorithm implicitly involves the ideal structure of the number field of the polynomial; it takes advantage of the theorem that any prime ideal above some rational prime p can be written as ${\displaystyle p\mathbb {Z} [\alpha ]+(u+v\alpha )\mathbb {Z} [\alpha ]}$. One then picks many prime numbers q of 적절한 크기(대개 요인 기준 한계 바로 위에 있음)를 적용하고 다음을 수행하십시오.

각 ${\displaystyle q}$에 대해 $G{\displaystyle }$ ${\displaystyle F}$( q ) {\$displaystyle GF(q)}$에 대해 다항식 f(a,b)를 인수하여 q 위의 primary 이상을 나열하십시오$.$

이러한 기본 이상 $각각{\displaystyle \mathfrak{}}$ '특수$q$ {\$displaystyle$ {\mathfak$\{$$q$$}$s}s'라고 하는 각 기본 이상에 대해 ${\displaystyle \mathbf{}}$ ${\$$\mathbf{x},\$$mathbf$$${$y$을$($를$)$ 구성하고 체 영역이라는 2차원 배열을 0으로 설정하십시오.

인자 베이스의$$ 각 주요 $이상{\displaystyle \mathfrak{}}$ p ${\$에 대해 ${\displaystyle \mathfrak{}}$ ${\displaystyle \mathfrak{q}}$ ${\displaystyle$ $\mathbf$ {$x} _{\mathfak{p},\mathbf$ {$y} _{\$$mathfrak {p}}}$을(으$$)로 생성한다.

충분히 큰 체 영역 내에 있는 이 하위 영역의 각 요소에 대해 해당 항목에 ${\displaystyle \mathrm{로그}}$${\displaystyle }$log ${\displaystyle p\mathfrak{}}$ $displaystyle \log {\mathfrak$ {$p}}을($를) 추가하십시오.

체 부위의 모든 항목을 충분히 큰 값으로 읽어라.

수 필드 체 적용의 경우, 두 다항식 모두 부드러운 값을 가져야 한다. 이 값은 두 다항식 모두에 대해 내측 루프를 실행하여 처리하며, 특수 q는 어느 한 쪽에서든 가져갈 수 있다.

가장 안쪽 루프의 처리

가장 안쪽 루프를 구현하는 데는 여러 가지 현명한 접근법이 있는데, 직사각형 영역 내에 격자 요소를 효율적으로 나열하는 것 자체가 비교가 되지 않는 문제이며, 캐시 구조를 활용하기 위해 체 영역으로 업데이트를 효율적으로 결합하는 것도 또 다른 비교 문제가 되기 때문이다.첫 번째에 대한 일반적인 해결책은 두 개의 발전기가 정의한 격자점을 주문하여 한 격자점에서 다음 격자 지점으로 이동하는 의사결정 규칙이 간단하도록 하는 것이다. 두 번째에 대한 일반적인 해결책은 크기보다 작은 배열의 하위 영역에 대한 일련의 업데이트 목록을 수집하는 것이다.레벨 2 캐시, L1 캐시의 라인 개수가 대략적이어서 목록에 항목을 추가하는 것은 일반적으로 캐시 적중으로 간주되고 업데이트 목록을 한 번에 하나씩 적용하며, 각 애플리케이션은 레벨 2 캐시 적중으로 처리된다.이를 효율적으로 수행하려면 최소한 체 어레이의 크기와 유사한 다수의 업데이트를 저장할 수 있어야 하므로 메모리 사용량이 상당히 많을 수 있다.

참조