Wheel factorization

Original article: w:Wheel factorization

Wheel factorization with n=2x3x5=30. No primes will occur in the yellow areas.

바퀴 인수분해(Wheel factorization)는 정수 인수분해(integer factorization)를 위한 시행 나눗셈(trial division) 방법의 개선입니다.

시행 나눗셈 방법은 연속적으로 인수분해될 숫자를 첫 번째 정수 (2, 3, 4, 5, ...)로 약수를 찾을 때까지 나누는 것입니다. 바퀴 인수분해에 대해, 우리는 기저(basis)라고 불리는 작은 숫자의 목록 — 일반적으로 처음 몇 개의 소수(prime numbers)로 시작합니다; 그런-다음 기저의 모든 숫자와 서로소(coprime)인 정수의, 바퀴(wheel)라고 불리는, 목록을 생성합니다. 그런-다음 인수분해될 숫자의 가장 작은 약수를 찾기 위해, 기저와 바퀴에서 숫자로 연속적으로 나눕니다.

{2, 3}을 기저와 함께, 이 방법은 나눗셈의 숫자를 시행 나눗셈에 필요한 숫자의 1/3 < 34%로 줄입니다. 더 큰 기저는 이 비율을 더욱 감소시킵니다; 예를 들어, {2, 3, 5} 기저와 함께 8/30 < 27%로; 그리고 기저 {2, 3, 5, 7}와 함께 48/210 < 23%로 줄입니다.

A typical example

처음 몇 개의 소수 {2, 3, 5}를 기저와 함께, 바퀴의 "첫 번째 회전"은 다음과 같이 구성됩니다:

7, 11, 13, 17, 19, 23, 29, 31.

두 번째 회전은 첫 번째 회전의 숫자에, 기저의 곱(product), 30을 더함으로써 얻습니다. 세 번째 회전은 두 번째 회전에 30을 더함으로써 얻습니다.

방법을 구현하는 데, 바퀴의 두 연속 원소 사이의 증분, 즉, 다음이

inc = [4, 2, 4, 2, 4, 6, 2, 6],

각 회전 후에 같게 남게 됨을 주목할 수 있습니다.

다음 제안된 구현은 n이 k로 균등하게 나누어지는지 여부를 테스트하고, 이 경우에서 true를 반환하고, 그렇지 않으면 false를 반환하는 보조 함수 div(n, k)를 사용합니다. 이 구현에서, 분해될 숫자는 n이고, 프로그램은 n의 가장 작은 약수를 반환합니다 – 만약 그것이 소수이면 n 자체를 반환합니다.

if div(n, 2) = true then return 2
if div(n, 3) = true then return 3
if div(n, 5) = true then return 5
k := 7; i := 0
while k * k ≤ n do
    if div(n, k) = true, then return k
    k := k + inc[i]
    if i < 7 then i := i + 1 else i := 0
return n

정수의 완전한 인수분해를 얻기 위해, 처음부터 바퀴를 다시 시작하지 않고 계산을 계속할 수 있습니다. 이것은 완전한 인수 분해를 위한 다음 프로그램으로 이어지며, 여기서 "add" 함수는 목록이어야 하는 두 번째 인수의 끝에 첫 번째 인수를 추가합니다.

factors := [ ]
while div(n, 2) = true do
    factors := add(2, factors)
    n := n / 2
while div(n, 3) = true do
    factors := add(3, factors)
    n := n / 3
while div(n, 5) = true do
    factors := add(5, factors)
    n := n / 5
k := 7; i := 0
while k * k ≤ n do
    if div(n, k) = true then 
        add(k, factors)
        n := n / k
    else
        k := k + inc[i]
        if i < 7 then i := i + 1 else i := 0
if n > 1 then add(n, factors)
return factors

Another presentation

바퀴 인수분해는 간단한 수학 형식과 훨씬 작은 첫 번째 소수의 목록에서 주로 소수의 목록을 생성하는 데 사용됩니다. 이들 목록은 그런-다음 시행 나눗셈(trial division) 또는 체(sieves)에서 사용될 수 있습니다. 이들 목록에서 모든 숫자가 소수는 아니기 때문에, 그렇게 하면 비효율적인 중복 연산이 발생합니다. 어쨌든, 생성기 자체는 순수하게 소수의 목록을 유지하는 것과 비교하여 매우 적은 메모리를 필요로 합니다. 초기 소수의 작은 목록은 목록의 나머지를 생성하기 위한 알고리듬(algorithm)에 대해 완전한 매개변수를 구성합니다. 이들 생성기는 바퀴(wheels)라고 참조됩니다. 각 바퀴는 무한한 숫자의 목록을 생성할 수 있지만, 특정 지점을 지나면 숫자는 대부분 소수가 아닙니다.

그 방법은 더 정확한 바퀴를 생성하기 위해 소수 바퀴 체(wheel sieve)로서 재귀적으로 적용될 수 있습니다. 바퀴 인수분해, 및 바퀴 체를 사용하는 바퀴 인수분해, 체에 대한 많은 결정적인 연구는 폴 프리처드(Paul Pritchard)에 의해 일련의 서로 다른 알고리듬을 공식화하는 데 수행되었습니다. 인수분해 바퀴의 사용을 시각화하기 위해, 인접한 다이어그램에 표시된 대로 원 주위에 자연수를 쓺으로써 시작할 수 있습니다. 바퀴-살의 숫자는 소수가 더 적은 숫자의 살에 축적되는 경향이 있도록 선택됩니다.

Sample graphical procedure

1. 인수분해 바퀴의 기저를 형성하기 위해 처음 몇 개의 소수를 찾으십시오. 그것들은 더 작은 인수분해 바퀴의 이전 응용에서 또는 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하여 그것들을 빠르게 찾음으로써 알려지거나 아마도 결정됩니다.
2. 기저 소수를 함께 곱하여 인수분해 바퀴의 원주인 결과 n을 제공합니다.
3. 1부터 n까지의 숫자를 원 안에 적으십시오. 이것은 바퀴의 한 회전을 나타내는 가장-안쪽 원이 될 것입니다.
4. 가장-안쪽 원의 숫자 1부터 n까지, 2단계에서 적용한 1단계에서 기저 소수의 모든 배수를 제거합니다. 이 합성수 제거는 에라토스테네스의 체와 같은 체를 사용하거나 더 작은 인수분해 바퀴의 적용의 결과로 달성될 수 있습니다.
5. 지금까지 쓴 원의 숫자를 x로 취하여, xn + 1이 (x − 1)n + 1와 같은 위치에 있음을 만족하는 가장-안쪽 원을 중심으로 동심원에 xn + 1에서 xn + n까지 계속 씁니다.
6. 가장 큰 회전 원이 소수성에 대한 테스트되도록 가장 큰 숫자에 걸쳐질 때까지 5단계를 반복합니다.
7. 숫자 1을 지웁니다.
8. 가장-안쪽 원 (원 1)에 있는 소수를 지우지 않고 모든 외부 원에서 1단계에서 찾은 소수의 살을 제거하고 2단계에서 적용합니다.
9. 8단계에서 기저 소수의 살을 제거하는 것과 같은 방법으로 4단계에서 내부 원 1에서 제거된 소수의 모든 배수의 살을 제거합니다.
10. 바퀴에서 남아있는 숫자는 대부분 소수입니다 (그것들은 집합적으로 "상대적으로" 소수라고 불립니다). 에라토스테네스의 체와 같은 다른 방법을 사용하거나 더 큰 인수분해 바퀴 추가로 적용하여 나머지 비-소수를 제거합니다.

Example

Wheel factorization with n=2x3=6

1. 처음 두 개의 소수: 2 및 3을 찾습니다.

2. n = 2 × 3 = 6

3.

 1  2  3  4  5  6

4. 2의 인수로 4와 6인 2와 3의 인수를 제거합니다; 3의 유일한 인수로 6은 이미 제거되었습니다:

 1  2  3  4  5  6

5. x = 1. xn + 1 = 1 · 6 + 1 = 7. (x + 1)n = (1 + 1) · 6 = 12. 7을 1에 맞추어서 7에서 12까지 씁니다.

 1  2  3  4  5  6
 7  8  9 10 11 12

6. x = 2. xn + 1 = 2 · 6 + 1 = 13. (x + 1)n = (2 + 1) · 6 = 18. 13에서 18까지 씁니다. 다음 몇 줄을 반복합니다.

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

7 및 8. 체질

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

9. 체질

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30

10. 결과 목록은 5²인 25의 비-소수 숫자를 포함합니다. 체와 같은 다른 방법을 사용하여 그것을 제거하여 다음에 도달합니다:

2 3 5 7 11 13 17 19 23 29

정확히 5개의 바퀴 주기의 다음 소수를 사용하고 결과 목록에서 해당 소수의 배수 (및 해당 소수만)를 제거함으로써, 우리는 2, 3, 및 5의 기저 소수를 갖는 인수분해 바퀴에 대해 4단계에 따라 기저 바퀴를 얻었음을 주목하십시오; 이것은 이전의 2/3 인수분해 바퀴보다 한 바퀴 앞선 것입니다. 그런-다음 7주기의 다음 후속 소수를 사용하고 10단계에서 결과 목록에서 7의 배수만 제거하여 10단계로 단계를 수행할 수 있습니다 (이 경우와 모든 후속 경우에서 일부 "상대적" 소수는 남겨둡니다 - 즉 일부는 진정한 정규화된 소수가 아닙니다). 완전한 자격을 갖춘 프라임), 다음으로 나아가서 고급 바퀴를 얻기 위해 필요에 따라 단계를 재귀적으로 반복하여 연속적으로 더 큰 바퀴를 얻습니다.

Analysis and computer implementation

형식적으로, 그 방법은 다음과 같은 통찰력을 사용합니다: 첫째, (무한한) 서로소의 집합과 결합된 기저 소수의 집합은 소수의 초월-집합입니다. 둘째, 해당 서로소의 무한 집합은 서로소에서 2와 기저 집합 곱 사이의 기저 집합까지 쉽게 열거될 수 있습니다. (1은 특별한 처리가 필요함을 주목하십시오.)

위의 예에서 볼 수 있듯이, 4단계에서 10단계까지 위의 재귀 절차를 반복 적용한 결과는 원하는 체질 범위 (잘릴 수 있음)에 걸쳐 있는 바퀴의 목록이 될 수 있고 결과 목록은 그런-다음 마지막으로 사용된 기저 소수보다 1보다 큰 소수의 배수만 포함됩니다.

일단 바퀴가 체질 범위의 원했던 위쪽 극한에 도달하면, 추가 바퀴 생성을 중지하고 해당 바퀴에서 정보를 사용하여 에라토스테네스의 체 유형 기술을 사용하지만 중복 추림을 피하기 위해 바퀴 고유의 틈 패턴을 사용하여 해당 마지막 바퀴 목록에서 남아있는 합성수를 추려낼 수 있음을 주목하십시오; 일부 최적화는 합성수의 반복 추림이 없다는 사실 (다음 섹션에서 입증될 것임)에 기반하여 이루어질 가능성이 있습니다: 남아있는 각 합성수는 정확히 한 번 추림될 것입니다. 대안적으로 원하는 체 범위의 제곱근까지 소수를 사용하여 잘린 바퀴 목록을 계속 생성할 수 있으며, 이 경우에서 바퀴에서 남아있는 모든 숫자 표현은 소수가 될 것입니다; 어쨌든, 비록 이 방법이 합성수를 한 번 이상 추림하지 않는 만큼 효율적이지만, 연속적인 바퀴 쓸기를 처리하는 데 일반적으로 고려되는 추림 연산 외부에서 많은 시간을 낭비하여 훨씬 더 오래 걸립니다. 인수분해 바퀴에 의한 합성수 제거는 다음을 기반으로 합니다: 숫자 k > n이 주어지면, k mod n과 n이 상대적으로 소수가 아니면 k가 소수가 아님을 압니다. 그로부터, 바퀴 체가 제거하는 숫자의 일부는 1 - phi (n) / n으로 결정될 수 있으며, 이는 체의 효율성이기도 합니다 (비록 모든 것이 물리적으로 제거될 필요는 없지만; 많은 것이 더 작은 바퀴를 더 큰 바퀴로 복사하는 연산에서 자동으로 추림될 수 있습니다).

다음이라고 알려져 있습니다:

$\lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }\sim 0.56145948,$

여기서 γ는 오일러 상수(Euler's constant)입니다. 따라서 phi(n) / n은 n이 무한대로 증가함에 따라 천천히 영으로 가고 무한하게 큰 n에 대해 이 효율이 100%까지 매우 느리게 상승함을 알 수 있습니다. phi의 속성에서, x보다 작은 가장 효율적인 체는 $n=p_{1}p_{2}...p_{i}<x$와 $np_{i+1}\geq x$인 체임을 쉽게 알 수 있습니다 (즉, 바퀴 생성은 마지막 바퀴가 지나갈 때 또는 체질 범위에서 가장 높은 숫자를 포함하기에 충분한 둘레를 가질 때 중지될 수 있습니다).

컴퓨터에서 최대로 사용하기 위해, 우리는 n보다 작고 그것에 상대적으로 소수인 숫자를 집합으로 원합니다. 몇 가지 관찰을 사용하여, 그 집합은 쉽게 생성될 수 있습니다:

1. 첫 번째 소수로 2를 갖는 $n=1$에 대한 그 집합인 $S_{1}=\{1\}$부터 시작합니다. 이 초기 집합은 바퀴 둘레가 1이므로 2부터 시작하는 모든 숫자가 "상대적" 소수로 포함됨을 의미합니다.
2. 다음 집합은 $S_{2}=\{1\}$이며, 이는 제거된 2의 인수 (2의 둘레)를 갖는 모든 홀수에 대해 3에서 시작하고, $S_{6}=\{1,5\}$는 위의 예제에서 초기 기저 바퀴에 대한 것처럼 제거된 2와 3의 인수 (6의 둘레)를 가지고, 기타 등등을 의미합니다.
3. $S_{n}+k$를 $k$가 $S_{n}$의 각 원소를 더해진 집합이라고 놓습니다.
4. 그런-다음 $S_{np_{i+1}}=F_{p_{i+1}}[S_{n}\cup S_{n}+n\cup S_{n}+2n\cup ...\cup S_{n}+n(p_{i+1}-1)]$이며, 여기서 $F_{x}$는 x의 모든 배수를 제거하는 연산을 나타냅니다.
5. 비록 알고리듬이 후속 집합에 더 이상 포함되지 않는 모든 제거된 기저 소수의 기록을 유지해야 하지만 $n>2$가 개별적으로 소수를 계산할 필요성을 제거할 때 1과 $p_{i+1}$는 $S_{n}$ 중 두 개의 가장 작은 것일 것입니다.
6. 원주 n > 2인 모든 집합은 $n/2$ 주위에서 대칭적이며, 저장소 요구 사항을 줄입니다. 다음 알고리듬은 이 사실을 사용하지 않지만, 각 집합에서 연속 숫자 사이의 틈이 중간 지점을 중심으로 대칭적이라는 사실을 기반으로 합니다.

See also

• Sieve of Sundaram
• Sieve of Atkin
• Sieve theory

External links

• Wheel Factorization
• Improved incremental prime number sieves by Paul Pritchard