소수는 1 보다 큰 자연수 (일부 정의에는 0 의 양의 정수가 포함되는 경우도 있음) 로, 두 개의 작은 수를 곱해서 얻을 수 없습니다. 소수수의 한 예는 숫자 1 과 7 을 곱해서 형성될 수 있기 때문에 7 이다. 다른 예로는 2, 3, 5, 11 등이 있습니다.
1 보다 큰 다른 두 자연수와 함께 구성할 수 있는 수를 합수라고 합니다. 이런 예는 4, 6, 9 와 같은 숫자를 포함한다.
산수의 기본 정리로 인해 소수는 수론에서 광범위하게 사용된다. 이 정리는 1 보다 큰 자연수가 소수이거나 소수수의 곱으로 분해될 수 있음을 보여준다. 예를 들어, 숫자 60 은 다음과 같은 소수의 곱으로 분해될 수 있습니다.
60 = 5 × 3 × 2 × 2
위의 예에서 알 수 있듯이 인수 분해에는 합수가 없다.
품질 요소 분해란 무엇입니까?
질계수 분해는 합수를 소수로 분해하는 곱이다. 많은 인수 분해 알고리즘이 있고, 어떤 것은 다른 알고리즘보다 더 복잡하다.
재판정:
합수의 질계수를 구하는 한 가지 방법은 나눗셈을 시도하는 것이다. 나눗셈은 매우 번거롭지만 더 기본적인 알고리즘 중 하나이다. 여기에는 논의 된 합수를 정수로 나누어 각 정수를 테스트하고 정수를 몇 번이나 나눌 수 있는지 결정하는 작업이 포함됩니다. 간단한 예로, 다음은 시험 나눗셈을 사용하는 820 의 질계수 분해입니다.
820 ÷ 2 = 410
410 ÷ 2 = 205
205 는 더 이상 2 로 나눌 수 없으므로 다음 정수를 테스트해 주세요. 205 는 3 으로 나눌 수 없습니다. 4 는 소수가 아닙니다. 그러나 5 로 나눌 수 있습니다.
205 ÷ 5 = 41
41 은 소수이기 때문에 재판분정은 이렇게 끝났다. 그래서:
820 = 41 × 5 × 2 × 2
제품도 다음과 같이 쓸 수 있습니다.
820 = 41 × 5 × 22
이것은 기본적으로 숫자의 질계수를 결정하는' 만력' 방법이다. 820 은 간단한 예이지만 곧 매우 번거로워질 수 있다.
소수 분해:
품질 요소 분해를 수행하는 또 다른 일반적인 방법은 품질 요소 분해라고 하며 요소 트리 사용과 관련될 수 있습니다. 계수 트리 생성에는 합수를 합수로 나누는 계수가 포함되며 모든 수가 소수가 될 때까지 포함됩니다. 다음 예에서는 820 을 품질 계수 2 로 나누어 품질 계수를 찾은 다음 모든 요소가 품질 계수가 될 때까지 결과를 계속 나눕니다. 다음 예에서는 숫자 820 을 사용하여 계수 트리를 생성하는 두 가지 방법을 보여 줍니다.
따라서, 어느 경우든, 820 의 질인자 분해는 다음과 같습니다.
820 = 41 × 5 × 2 × 2
이러한 방법은 더 작은 숫자 (다른 많은 알고리즘 포함) 에 적합하지만, 훨씬 큰 숫자에 대해서는 아직 알려진 알고리즘이 없습니다. 기계가 더 큰 숫자의 질적 요소 분해를 계산하는 데도 시간이 오래 걸립니다. 2009 년에 과학자들은 수백 대의 기계를 사용하여 232 비트 디지털 RSA-768 을 인수 분해하는 프로젝트를 완료했는데, 이 프로젝트는 2 년이 걸렸다.
