소인수분해

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 소인수분해 알고리즘
3. 소인수분해의 복잡도
- 3.1. 시간 복잡도
- 3.2. 복잡도 클래스
4. 정수환에서의 소인수분해
- 4.1. 소원과 기약원
- 4.2. 일의 분해 환 (UFD)
5. 소인수분해 연구 및 기록
참조

1. 개요

소인수분해는 1보다 큰 정수를 소수의 곱으로 나타내는 것으로, 현대 전자기 컴퓨터에서는 다항 시간 내에 해결하는 알고리즘이 알려져 있지 않다. 양자 컴퓨터에서는 쇼어 알고리즘을 통해 다항 시간 내에 소인수분해가 가능하지만, 아직까지 어떤 합성수를 다항 시간 안에 소인수분해하기는 어려운 문제이다. 소인수분해의 난해함은 RSA 암호와 같은 현대 암호의 핵심이다. 소인수분해 알고리즘에는 시도 나누기법과 폴라드 로 소인수분해법, 타원 곡선법 등이 있다. 소인수분해 문제는 NP와 co-NP에 속하며, 양자 컴퓨터의 쇼어 알고리즘 때문에 BQP에도 속한다. 정수환에서의 소인수분해는 가환환에서 나누어떨어짐의 관계를 통해 정의되며, 기약원과 소원의 개념이 중요하다. 커닝햄 프로젝트와 RSA-240, RSA-250 등의 소인수분해 기록이 있으며, 양자 컴퓨터를 이용한 소인수분해 성공 사례도 존재한다.

더 읽어볼만한 페이지

컴퓨터 과학의 미해결 문제 - 인공지능
인공지능은 인간의 지능적 행동을 모방하는 컴퓨터 시스템으로, 인간 수준의 일반 지능을 가진 강인공지능과 특정 문제 해결에 특화된 약인공지능으로 나뉘며, 딥러닝 기술 발전으로 다양한 분야에서 성과를 거두고 있지만 윤리적, 사회적 문제에 대한 고려가 필요하다.
컴퓨터 과학의 미해결 문제 - 이산 로그
이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
인수분해 - 산술의 기본 정리
산술의 기본 정리는 1보다 큰 모든 양의 정수를 소수의 곱으로 유일하게 표현할 수 있다는 정리이다.
인수분해 - 행렬 분해
행렬 분해는 주어진 행렬을 특정 성질을 갖는 여러 행렬의 곱으로 표현하는 방법으로, 수치 해석에서 행렬 알고리즘 구현 및 선형 연립 방정식 해를 구하거나 행렬 특성 분석에 활용되며 LU 분해, QR 분해, 특잇값 분해 등이 있다.
소인수 분해 알고리즘 - 쇼어 알고리즘
쇼어 알고리즘은 소인수분해 및 이산 로그 문제를 해결하는 양자 알고리즘으로, 양자 위상 추정 알고리즘과 연분수 알고리즘을 활용하며, 공개 키 암호화 방식을 깨뜨릴 수 있다.
소인수 분해 알고리즘 - 연분수 소인수분해 알고리즘
연분수 소인수분해 알고리즘은 합성수 $n$ 의 제곱근을 연분수로 전개하여 얻은 값으로 $x^2 \equiv y^2 \pmod n$ 를 만족하는 $x$ 와 $y$ 를 찾아 $n$ 의 약수를 구하는 알고리즘이다.

소인수분해

2. 소인수분해 알고리즘

산술의 기본 정리에 의해 모든 양의 정수는 소수들의 곱으로 표현하는 방법이 (곱셈의 교환법칙을 제외하면) 유일하게 존재한다. 그러나 산술의 기본정리는 그 소인수분해를 하는 방법을 알려주지는 않는다. 단지 존재성을 확인해 줄 뿐이다.^[1]

현대의 전자기 기반 컴퓨터상에서 소인수분해에 대한 다항식 시간 알고리즘은 알려져 있지 않다. 단, 이론적인 양자컴퓨터에서의 쇼어의 알고리즘은 다항 시간안에 소인수 분해가 가능하다. 하지만 아직까지 어떤 합성수를 다항 시간 안에 소인수분해하기는 어려운 문제이며, 예를 들어 193자리 수(RSA-640)는 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다. 소인수분해의 난해함은 RSA와 같은 현대 암호의 핵심적 부분이 된다.

산술의 기본 정리에 따르면, 모든 양의 정수는 고유한 소인수분해를 갖는다. 정수가 소수인지 여부를 테스트하는 것은 다항 시간에 수행할 수 있으며, 예를 들어 AKS 소수 판별법을 사용한다.

2. 1. 고전적 알고리즘

고전적인 소인수분해 알고리즘은 대부분 페르마 소정리를 확장한 것을 이용한다.^[2] 윌리엄의 p+1 알고리즘, 폴라드의 p-1 알고리즘, 폴라드 로 알고리즘, 페르마의 알고리즘 등이 여기에 속한다.

bit|비트^영어 숫자 중에서, 기존 알고리즘을 사용하여 실제 인수분해하기 가장 어려운 것은 인수가 비슷한 크기인 반소수이다. 이러한 이유로, 이러한 정수는 암호 응용 프로그램에 사용된다.

2019년에는 폴 짐머만을 포함한 연구팀이 약 900 코어-년의 계산 능력을 활용하여 240자리(795비트) 숫자(RSA-240)를 인수분해했다.^[2] 이 연구자들은 1024비트 RSA 모듈러스는 약 500배 더 오래 걸릴 것으로 추정했다.^[3]

가장 큰 반소수 인수분해는 2020년 2월에 829비트 숫자이자 250자리 십진수인 RSA-250이었다. 총 계산 시간은 인텔 제온 골드 6130 2.1 GHz를 사용하여 약 2700 코어-년의 계산 시간이 걸렸다.

특수 목적 소인수분해 알고리즘의 실행 시간은 소인수분해할 숫자의 속성이나 알려지지 않은 인수 중 하나(크기, 특수한 형태 등)에 따라 달라진다. 실행 시간을 결정하는 매개변수는 알고리즘마다 다르다.

특수 목적 소인수분해 알고리즘의 중요한 하위 분류는 실행 시간이 가장 작은 소인수의 크기에 따라 달라지는 '범주 1' 또는 '제1 범주' 알고리즘이다. 알려지지 않은 형태의 정수가 주어지면, 이러한 방법은 일반적으로 작은 인수를 제거하기 위해 범용 방법 전에 적용된다.^[10] 예를 들어, 단순한 나눗셈 시도는 범주 1 알고리즘이다.

범주 1 알고리즘에는 다음이 포함된다.

나눗셈 시도
휠 인수분해
폴라드 로 알고리즘
대수적 그룹 인수분해 알고리즘
페르마 인수분해 방법
오일러의 인수분해 방법
특수 수체 체
두 제곱의 차이

범용 인수 분해 알고리즘은 "Category 2", "Second Category" 또는 크레이칙 "family" 알고리즘이라고도 하며,^[10] 인수 분해할 정수의 크기에만 의존하는 실행 시간을 갖는다. 이는 RSA 수를 인수 분해하는 데 사용되는 알고리즘 유형이다. 대부분의 범용 인수 분해 알고리즘은 제곱 합동 방법에 기반한다.

범용 인수 분해 알고리즘에는 다음이 포함된다.

딕슨의 인수 분해 방법
연분수 인수 분해 (CFRAC)
2차 체
유리수 체
일반 수체 체
섕크스의 제곱 형태 인수 분해 (SQUFOF)

양의 정수 N을 소인수분해하는 가장 단순한 방법은 2부터 차례대로 N의 제곱근까지의 소수로 나누어보는 방법(시도 나누기법)이다.^[16] 하지만, N이 커지면 이 방법으로는 어렵다.

큰 N에 대해서는 다음과 같은 방법이 있다.

로 법 (폴라드 로 소인수분해법)
p-1 법
p+1 법
연분수법
타원 곡선법 (ECM, Elliptic curve method)
다중 다항식 2차 체법 (MPQS, Multiple polynomial quadratic sieve)
수체 체법 (NFS, Number field sieve)
일반 수체 체법 (GNFS, General number field sieve)
특수 수체 체법 (SNFS, Special number field sieve)

2. 2. 현대적 알고리즘

암호학의 발달과 함께 소인수분해 방법도 발전해 왔으며, 그중 가장 효율적인 알고리즘들은 다음과 같다.

렌스트라의 타원곡선 알고리즘(ECM): 타원곡선의 성질을 이용하여 어떤 수를 소인수분해하는 알고리즘으로, 가장 작은 소인수의 크기에 따라서 실행 시간이 결정된다. 실행 시간은 $O\left(\exp\left(\sqrt{2 \ln(p \ln( \ln(p))}\right)\right)$ 로, 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.
수체 체(GNFS) 알고리즘은 이차 체 알고리즘을 발전시킨 것으로, 일반 컴퓨터로 실행시킬 수 있는 알고리즘 중에서는 가장 빠른 알고리즘이다. b가 합성수의 비트수일 때, 이 알고리즘은 $O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)$ 의 시간복잡도를 가진다.
특수 수체 체(SNFS) 알고리즘은 r, e, s가 자연수일 때, r^e ± s 꼴인 자연수에 대해서 작동하는 알고리즘이다. r, s의 값이 커지면 속도가 급속도로 느려지기 때문에 r, s가 작은 자연수에 대해서만 잘 작동하며 사용할 수 있다.
다중 다항식 이차체(MPQS) 알고리즘은 이차 체 알고리즘을 확장시킨 알고리즘으로, 한 개의 함수를 이용하는 이차 체와는 달리 여러 개의 함수를 이용하는 알고리즘이다.
이차 체(QS) 알고리즘은 100자리 이하의 자연수를 소인수분해할 때 적합하며, 보통 어떤 합성수의 소인수들의 크기가 비슷할 때 잘 작동한다.

기존 알고리즘을 사용하여 실제 인수분해하기 가장 어려운 것은 인수가 비슷한 크기인 반소수이다. 이러한 이유로, 이러한 정수는 암호 응용 프로그램에 사용된다.

2019년에는 폴 짐머만을 포함한 연구팀이 약 900 코어-년의 계산 능력을 활용하여 240자리(795비트) 숫자(RSA-240)를 인수분해했다.^[2] 연구자들은 1024비트 RSA 모듈러스는 약 500배 더 오래 걸릴 것으로 추정했다.^[3]

가장 큰 반소수 인수분해는 2020년 2월에 829비트 숫자이자 250자리 십진수인 RSA-250이었다. 총 계산 시간은 인텔 제온 골드 6130 2.1 GHz를 사용하여 약 2700 코어-년의 계산 시간이 걸렸다.

특수 목적 소인수분해 알고리즘의 실행 시간은 소인수분해할 숫자의 속성이나 알려지지 않은 인수 중 하나(크기, 특수한 형태 등)에 따라 달라진다. 실행 시간을 결정하는 매개변수는 알고리즘마다 다르다.

특수 목적 소인수분해 알고리즘의 중요한 하위 분류는 실행 시간이 가장 작은 소인수의 크기에 따라 달라지는 ''범주 1'' 또는 ''제1 범주'' 알고리즘이다. 알려지지 않은 형태의 정수가 주어지면, 이러한 방법은 일반적으로 작은 인수를 제거하기 위해 범용 방법 전에 적용된다.^[10] 예를 들어, 단순한 나눗셈 시도는 범주 1 알고리즘이다.

나눗셈 시도
휠 인수분해
폴라드 로 알고리즘
대수적 그룹 인수분해 알고리즘
페르마 인수분해 방법
오일러의 인수분해 방법
특수 수체 체
두 제곱의 차이

범용 인수 분해 알고리즘은 "Category 2", "Second Category" 또는 크레이칙 "family" 알고리즘이라고도 하며,^[10] 인수 분해할 정수의 크기에만 의존하는 실행 시간을 갖는다. 이는 RSA 수를 인수 분해하는 데 사용되는 알고리즘 유형이다. 대부분의 범용 인수 분해 알고리즘은 제곱 합동 방법에 기반한다.

딕슨의 인수 분해 방법
연분수 인수 분해(CFRAC)
2차 체
유리수 체
일반 수체 체
섕크스의 제곱 형태 인수 분해(SQUFOF)
쇼어의 알고리즘

큰 수에 대해서는 다음과 같은 방법이 있다.

폴라드 로 소인수분해법
연분수법
타원 곡선법 (ECM)
다중 다항식 2차 체법(MPQS)
수체 체법(NFS)
일반 수체 체법(GNFS)
특수 수체 체법(SNFS)

2. 3. 양자 알고리즘

쇼어의 알고리즘은 양자 컴퓨터를 사용하여 소인수분해 문제를 다항 시간 안에 풀 수 있는 알고리즘이다.

양자 컴퓨터를 이용해 소인수분해에 성공한 기록은 다음과 같다.

연도	분해된 숫자	비고
2001년	15 (=3×5)	IBM
2012년	21 (=3×7)	브리스톨 대학교

3. 소인수분해의 복잡도

현대 컴퓨터로는 소인수분해를 다항식 시간 알고리즘으로 해결하는 방법이 알려져 있지 않다. 그러나 양자컴퓨터에서는 쇼어의 알고리즘을 이용하면 다항 시간 안에 소인수분해가 가능하다. 현재까지 합성수를 다항 시간 안에 소인수분해하는 것은 어려운 문제로 남아있다. 예를 들어 193자리 수(RSA-640)는 2.2 GHz 옵테론 CPU 30개를 5개월 동안 사용해야 소인수분해할 수 있었다. 이처럼 소인수분해가 어렵다는 점은 RSA 등 현대 암호 체계의 기반이 된다.

고전적인 소인수분해 알고리즘은 대부분 페르마 소정리를 확장한 것이다. 자주 사용되는 알고리즘에는 윌리엄의 p+1 알고리즘, 폴라드의 p-1 알고리즘, 폴라드 로 알고리즘, 페르마의 알고리즘 등이 있다.

3. 1. 시간 복잡도

현대의 전자기 기반 컴퓨터상에서 소인수분해에 대한 다항식 시간 알고리즘은 알려져 있지 않다. 단, 이론적인 양자컴퓨터에서의 다항식 시간 소인수분해 알고리즘(쇼어의 알고리즘)은 존재한다.^[4]^[5] 하지만 아직까지 어떤 합성수를 다항 시간 안에 소인수분해하기는 어려운 문제이며, 일례로 193자리 수(RSA-640)는 5개월간 30개의 2.2 GHz 옵테론 CPU를 동원하여 소인수분해 되었다. 소인수분해의 난해함은 RSA와 같은 현대 암호의 핵심적 부분이 된다.

모든 양수에 대해 더 빠른, 즉 준지수 알고리즘은 발표되었다. 현재 이론적으로 최상의 점근적 실행 시간을 가진 알고리즘은 1993년에 처음 발표된 일반 수체 체 (GNFS)이며,^[6] 비트 숫자 에 대해 다음과 같은 시간 내에 실행된다.

:

\exp\left( \left(\left(\tfrac{8}{3}\right)^\frac{2}{3} + o(1)\right)\left(\log n\right)^\frac{1}{3}\left(\log \log n\right)^\frac{2}{3}\right).

암호학의 발달과 함께 소인수분해 방법도 발전해 왔으며 그중 가장 효율적인 알고리즘들을 간추리면 아래와 같다.

렌스트라의 타원곡선 알고리즘 (Elliptic Curve Method, ECM): 타원곡선의 성질을 이용하여 어떤 수를 소인수분해하는 알고리즘으로, 가장 작은 소인수의 크기에 따라서 실행 시간이 결정된다. 이 알고리즘의 실행 시간은 $O\left(\exp\left(\sqrt{2 \ln(p \ln( \ln(p))}\right)\right)$ 로 이전의 잉여체의 성질을 이용한 알고리즘에 비해 매우 우수하다.
수체 체(General Number Field Sieve, GNFS) 알고리즘은 이차 체 알고리즘을 발전시킨 것으로 일반 컴퓨터로 실행시킬 수 있는 알고리즘 중에서는 가장 빠른 알고리즘이다. b가 합성수의 비트수일 때, 이 알고리즘은 $O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)$ 의 시간복잡도를 가진다.
특수 수체 체 (Special Number Field Sieve, SNFS) 알고리즘은 r, e, s가 자연수일 때, r^e ± s 꼴인 자연수에 대해서 작동하는 알고리즘이다. 여기서 r, s의 값이 커지면 속도가 급속도로 느려지기 때문에 r, s가 작은 자연수에 대해서만 잘 작동하며 사용할 수 있다.
다중 다항식 이차체 (Multiple Polynomial Quadratic Sieve, MPQS) 알고리즘은 이차 체 알고리즘을 확장시킨 알고리즘으로, 한 개의 함수를 이용하는 이차 체와는 달리 여러 개의 함수를 이용하는 알고리즘이다.
이차 체 (Quadratic Sieve, QS) 알고리즘은 100자리 이하의 자연수를 소인수분해할 때 적합하며, 보통 어떤 합성수의 소인수들의 크기가 비슷할 때 잘 작동한다.

현재 컴퓨터의 경우, GNFS는 큰 (약 400비트 이상)에 대해 가장 좋은 발표된 알고리즘이다. 그러나 양자 컴퓨터의 경우, 피터 쇼어는 1994년에 다항 시간 내에 해결하는 알고리즘을 발견했다. 쇼어의 알고리즘은 비트 숫자 입력에 대해 시간 와 공간 만을 사용한다. 2001년, 쇼어의 알고리즘은 7개의 큐비트를 제공하는 분자에 대해 핵자기 공명 기술을 사용하여 처음 구현되었다.^[7]

소인수분해를 수행하는 모든 정수를 다항 시간 내에 인수분해할 수 있는, 즉 비트 숫자 을 상수 에 대해 시간 안에 인수분해할 수 있는 알고리즘은 아직 발표되지 않았다.

복잡도 클래스 (예: P, NP, co-NP)에 대해 이야기하기 위해, 문제는 결정 문제로 제시되어야 한다.

이 문제는 NP와 co-NP 모두에 속하는 것으로 알려져 있으며, 이는 "예"와 "아니오" 답변 모두 다항 시간 내에 검증될 수 있음을 의미한다. "예" 답변은 인 인수분해를 제시하여 증명할 수 있으며 이다. "아니오" 답변은 을 모두 보다 큰 서로 다른 소수로 인수분해하여 증명할 수 있으며, AKS 소수성 검사를 사용하여 소수성을 검증한 다음 이를 곱하여 을 얻을 수 있다. 산술의 기본 정리는 허용될 증가하는 소수의 가능한 문자열이 하나뿐임을 보장하며, 이는 이 문제가 UP와 co-UP 모두에 속함을 보여준다.^[8] 쇼어의 알고리즘 때문에 BQP에도 속하는 것으로 알려져 있다.

이 문제는 복잡도 클래스 P, NP-완비,^[9] 및 co-NP-완비의 세 클래스 모두에 속하지 않는 것으로 의심된다. 따라서 NP-중간 복잡도 클래스의 후보이다.

반대로, 결정 문제 "은 합성수인가?" (또는 동등하게: "은 소수인가?")는 의 인수를 지정하는 문제보다 훨씬 쉬운 것으로 보인다. 합성/소수 문제는 AKS 소수성 검사를 사용하여 다항 시간 내에 (의 자릿수 에 대해) 해결할 수 있다. 또한, 오류의 극히 작은 가능성을 기꺼이 받아들인다면, 실제로 소수성을 매우 빠르게 테스트할 수 있는 여러 확률적 알고리즘이 있다. 소수성 검사의 용이성은 시작하기 위해 큰 소수를 찾아야 하므로 RSA 알고리즘의 중요한 부분이다.

3. 2. 복잡도 클래스

소인수분해 문제는 NP와 co-NP에 속하며, P, NP-완비, co-NP-완비에는 속하지 않는 것으로 추정된다.^[9] 따라서 NP-중간 복잡도 클래스의 후보이다.

소인수분해 문제는 "모든 자연수 과 에 대해, 이 1 외에 보다 작은 인수를 가지고 있는가?" 라는 결정 문제 형태로 바꿀 수 있다. 이 문제는 "예"와 "아니오" 답변 모두 다항 시간 내에 검증될 수 있으므로 NP와 co-NP 모두에 속한다. "예" 답변은 인 인수분해를 제시하여 증명할 수 있다. "아니오" 답변은 을 모두 보다 큰 서로 다른 소수로 인수분해하여 증명할 수 있다. 산술의 기본 정리는 가능한 소수 문자열이 하나뿐임을 보장하므로, 이 문제는 UP와 co-UP에도 속한다.^[8] 또한, 쇼어의 알고리즘 덕분에 BQP에도 속한다.

비트 숫자 을 상수 에 대해 시간 안에 인수분해할 수 있는 알고리즘은 아직 발표되지 않았으며, 일반적으로 존재하지 않을 것으로 추정된다.^[4]^[5] 그러나 모든 양수 에 대해 보다 빠른, 즉 준지수 알고리즘은 발표되었다. 현재 이론적으로 최상의 점근적 실행 시간을 가진 알고리즘은 일반 수체 체(GNFS)이다.^[6] 양자 컴퓨터의 경우, 피터 쇼어가 1994년에 다항 시간 내에 소인수분해를 해결하는 쇼어의 알고리즘을 발견했다.

한편, "n은 합성수인가?" (또는 "n은 소수인가?")라는 결정 문제는 의 인수를 찾는 문제보다 훨씬 쉬운 것으로 보인다. 이 문제는 AKS 소수성 검사를 사용하여 다항 시간 내에 해결할 수 있다.

4. 정수환에서의 소인수분해

정역에서 소인수분해(에 상당하는 개념)를 생각하는 문제는 대수학에서의 고전적인 문제 중 하나이다.

4. 1. 소원과 기약원

정역에서 소인수분해(에 상당하는 개념)를 생각하는 문제는 대수학에서의 고전적인 문제 중 하나이다.

일반적으로 가환환 ''R''에서는 "나누어떨어진다"라는 관계를 단항 아이디얼의 포함 관계에 의해 정할 수 있다. 즉, ''a'', ''b'' ∈ ''R''이 생성하는 단항 아이디얼 (''a'') = ''aR'', (''b'') = ''bR''에 대해, (''a'') ⊃ (''b'')일 때 ''a'' ''b''라고 쓰고, ''a''는 ''b''를 나누어떨어지게 한다, 또는 ''a''는 ''b''의 약원이다, 또는 ''b''는 ''a''의 배원이다 등으로 말한다. 바꿔 말하면, ''a''가 ''b''를 나누어떨어지게 한다는 것은, ''b'' = ''ac''를 만족하는, ''R''의 가역이며 0이 아닌 원소 ''c''가 존재한다는 것이다.

가역이면서 0이 아닌 ''R''의 원소가, 두 개의 비가역원의 곱으로 나타낼 수 있을 때, '''가약'''이라고 하며, 그렇지 않을 때 '''기약원'''이라고 한다. 단항 아이디얼 (''p'')가 자명하지 않은 소 아이디얼일 때, ''p''를 '''소원'''이라고 한다. '''소원'''은 '''기약원'''이지만, 일반적으로 역은 성립하지 않는다.

4. 2. 일의 분해 환 (UFD)

정역에서 소인수분해(에 상당하는 개념)를 생각하는 문제는 대수학에서의 고전적인 문제 중 하나이다.

환의 원소를 기약원의 곱으로 나타내는 것을 '''기약원 분해''', 소원의 곱으로 나타내는 것을 '''소원 분해'''라고 한다. 기약원 분해가 유일한 환을 일계수분해환 또는 소원분해정역이라고 한다 (임의의 원소가 소원의 곱으로 나타낼 수 있다면, 그 표현 방법은 유일하다). 유리수 전체로 구성된 환이나 체 위의 다항식 환 등은 일계수분해환이다. 이들 환은 유클리드 환이기도 하지만, 일반적으로 유클리드 정역은 단항 아이디얼 정역이며, 단항 아이디얼 정역은 일계수분해환이 된다.

일계수분해환이 아닌 예로, 유리수체에 방정식의 근을 첨가한 대수적 체의 정수환에서을 기약 분해하는 것을 생각해 보자. 정수의 범위에서는 (과 동치인 것) 뿐이지만, 의 범위에서는

:

와 본질적으로 다른 2가지 방법으로 기약 분해된다. 따라서 는 일계수분해환이 아니다. 그러나 아이디얼로서는, 또는는 더 분해될 수 있으며, 소 아이디얼의 곱으로서는 유일하게

:

로 분해된다. 일반적으로 대수적 체의 정수 환은 데데킨트 환이며, 소 아이디얼의 곱으로 유일하게 분해된다.

이러한 고찰은 쿠머의 이상수 이론에서 시작되었다고 여겨진다. 쿠머 이후, 데데킨트의 아이디얼론 등을 거쳐 대수적 정수론의 기반이 되었다.

5. 소인수분해 연구 및 기록

커닝햄 프로젝트(Cunningham Project)는 및 많은 자연수 에 대해, 을 소인수분해하려는 프로젝트이다.^[2]

연도	사건	내용
2005년 4월	의 약수로 나타나는 176자리 합성수 소인수분해	리쿄 대학, NTT, 후지쯔 연구소 공동 연구, General number field sieve^영어 사용
2005년 5월	200자리 합성수 RSA-200 (RSA 챌린지) 소인수분해	일반 수체 체법 (Bahr, Boehm, Franke, Kleinjung)
2006년 8월	에서 67자리의 소수 분해	타원 곡선법 (B. Dodson)
2006년 9월	의 약수로 나타나는 128자리 합성수 소인수분해	정보통신연구기구, 후지쯔, 후지쯔 연구소 공동 연구, 필드 프로그래머블 게이트 어레이 및 다이내믹 리컨피겨러블 프로세서를 사용한 전용 하드웨어 최초 사용
2007년 5월	의 약수로 나타나는 307자리 합성수 소인수분해	NTT, 독일 본 대학교, 스위스 연방 공과대학교 공동 연구, 특수 수체 체법 사용
2010년 1월	232자리(768비트) 수 소인수분해	NTT, 스위스 연방 공과대학교 로잔 (EPFL), 독일 본 대학교, 프랑스 국립 정보학 자동 제어 연구소 (INRIA), 네덜란드 국립 정보 공학·수학 연구소 (CWI) 공동 연구, 일반 수체 체법, 300대 PC 병렬 계산 처리 (약 3년 소요)
2019년	240자리(795비트) 숫자(RSA-240) 인수분해	폴 짐머만 포함 연구팀, 약 900 코어-년 계산 능력 활용
2020년 2월	829비트 숫자, 250자리 십진수 (RSA-250) 소인수분해	인텔 제온 골드 6130 2.1 GHz 사용, 약 2700 코어-년 계산 시간 소요

^[2]

참조

_[1] 간행물 Integer Factoring http://link.springer[...] Springer US 2022-06-22
_[2] 웹사이트 '[Cado-nfs-discuss] 795-bit factoring and discrete logarithms' https://lists.gforge[...]
_[3] conference Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings Springer
_[4] 간행물 The Proof is in the Pudding: The Changing Nature of Mathematical Proof https://books.google[...] Springer
_[5] 간행물 Computational complexity https://books.google[...] Cambridge University Press
_[6] 서적 The development of the number field sieve https://doi.org/10.1[...] Springer 2021-03-12
_[7] 학술지 Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
_[8] 웹사이트 Computational Complexity Blog: Complexity Class of the Week: Factoring http://weblog.fortno[...] 2002-09-13
_[9] 간행물 The Princeton Companion to Mathematics Princeton University Press
_[10] 서적 A Course in Computational Number Theory https://archive.org/[...] Key College Publishing/Springer
_[11] 학술지 Refined analysis and improvements on some factoring algorithms http://www.dtic.mil/[...]
_[12] 학술지 A probabilistic factorization algorithm with quadratic forms of negative discriminant
_[13] 학술지 Fast and rigorous factorization under the generalized Riemann hypothesis https://infoscience.[...]
_[14] 학술지 A Rigorous Time Bound for Factoring Integers https://www.ams.org/[...] 1992-07
_[15] URL https://www.imes.boj.or.jp/research/papers/japanese/kk18-b1-3.pdf
_[16] URL https://fussy.web.fc2.com/algo/math11_factorization.htm
_[17] 문서 제곱수를 썼을때, 일차식이 아닌 경우는 어떤 수의 제곱수 혹은 그의 배수들이다.

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com