큰 소수를 만드는 방법 | 콴타 매거진

소수는 까다로운 것입니다. 우리는 학교에서 그것들이 1과 자기 자신 외에 다른 인수가 없는 숫자라는 것과 수천 년 동안 수학자들이 무한한 수가 존재한다는 것을 알고 있다는 것을 배웁니다. 명령에 따라 생산하는 것이 어려운 것처럼 보이지 않습니다.

하지만 그것은. 임의로 큰 소수를 구성하는 것은 매우 복잡합니다. 기본적으로 두 가지 계산 옵션이 있으며 둘 다 단점이 있습니다. 임의성을 사용하고 추측하여 찾을 수 있지만 방법이 일관성이 없습니다. 매번 다른 소수를 생성할 위험이 있습니다. 또는 보다 안정적이고 결정론적인 알고리즘을 사용할 수 있지만 계산 비용이 많이 듭니다.

XNUMX월, 컴퓨터 과학자 팀 보여 일종의 하이브리드 접근 방식도 작동할 수 있습니다. 그들은 알고리즘을 여러 번 실행하더라도 동일한 소수를 전달할 확률이 높은 특정 길이의 소수를 출력하기 위해 무작위 및 결정론적 접근 방식을 효과적으로 결합한 알고리즘을 발표했습니다. 이 알고리즘은 임의성과 복잡성을 흥미로운 방식으로 연결하며 일부 인코딩 체계가 큰 소수의 구성에 의존하는 암호화에도 유용할 수 있습니다.

"그들은 각각 다른 길이의 소수를 구성하려고 시도하는 일련의 시도를 배치했으며 시도 중 하나가 작동한다는 것을 보여주었습니다."라고 말했습니다. 로에이 텔, 작업에 참여하지 않은 Institute for Advanced Study의 이론 컴퓨터 과학자. "결정론적으로 선택된 소수를 출력하는 구성이지만 그 과정에서 동전을 던지고 임의의 선택을 할 수 있습니다."

소수에 대한 효율적인 레시피를 만드는 문제는 뿌리가 깊습니다. 의사 난수 알고리즘을 연구하는 Ofer Grossman은 "우리는 소수가 어떻게 분포되어 있는지 또는 소수의 간격에 대해 그다지 많이 알지 못합니다."라고 말했습니다. 그리고 우리가 그것들을 어디서 찾을 수 있는지 모른다면 처음부터 소수를 생성하는 쉬운 방법이 없습니다.

시간이 지남에 따라 연구원들은 앞서 언급한 접근법을 개발했습니다. 가장 간단한 방법은 추측하는 것입니다. 예를 들어 1,000자리의 소수를 원하는 경우 1,000자리 숫자를 임의로 선택한 다음 확인할 수 있습니다. "만약 그것이 소수가 아니라면, 당신은 하나를 찾을 때까지 다른 하나를 시도하고 또 다른 것을 시도합니다."라고 말했습니다. 라훌 산타남, 옥스퍼드 대학의 컴퓨터 과학자이자 새 논문의 공동 저자. "소수가 많기 때문에 이 알고리즘은 상대적으로 적은 수의 반복 후에 높은 확률로 소수인 숫자를 제공합니다." 그러나 임의성을 사용한다는 것은 매번 다른 숫자를 얻을 가능성이 높다는 것을 의미한다고 그는 말했습니다. 일관성이 필요한 경우 문제가 될 수 있습니다. 예를 들어 큰 소수의 가용성에 의존하는 암호화 보안 방법을 사용하는 경우입니다.

다른 접근 방식은 결정적 알고리즘을 사용하는 것입니다. 시작점을 선택하고 우선 순위에 대해 순차적으로 숫자 테스트를 시작할 수 있습니다. 결국 당신은 하나를 찾을 운명이고 당신의 알고리즘은 당신이 찾은 첫 번째 것을 지속적으로 출력할 것입니다. 하지만 시간이 좀 걸릴 수 있습니다. 1,000자리의 소수를 찾고 있다면 2로 계산해도⁵⁰⁰ 우주의 나이보다 훨씬 오래 걸리는 단계는 성공을 보장하기에 충분하지 않습니다.

2009년에 수학자이자 필즈상 수상자인 Terence Tao는 더 잘하고 싶었습니다. 그는 수학자들에게 계산 시간 제한 내에서 주어진 크기의 소수를 찾기 위한 결정론적 알고리즘을 제시하도록 도전했습니다.

그 시간 제한은 다항식 시간으로 알려져 있습니다. 알고리즘은 걸리는 단계 수가 n, 입력 크기. (다항식 함수에는 n² 또는 4n³.) 소수 구성의 맥락에서, n 원하는 소수의 자릿수를 나타냅니다. 계산적으로 말해서 이것은 많은 비용이 들지 않습니다. 컴퓨터 과학자들은 다항식 시간에 알고리즘으로 해결할 수 있는 문제를 쉽게 설명합니다. 대조적으로 어려운 문제는 지수 함수(예: 2ⁿ).

수십 년 동안 연구원들은 무작위성과 경도 사이의 연관성을 조사했습니다. 소수 구성 문제는 임의성을 허용하면 쉬운 것으로 간주되었고 매번 다른 숫자를 받는 것에 만족했으며 결정론을 주장하면 어려운 것으로 간주되었습니다.

아직 아무도 Tao의 도전에 응하지 못했지만 새로운 작업이 가까워졌습니다. MIT의 컴퓨터 과학자인 Shafi Goldwasser와 Eran Gat가 2011년에 도입한 접근 방식에 크게 의존합니다. 그들은 "의사 결정론적(pseudodeterministic)" 알고리즘을 설명했습니다. 즉, 큰 소수를 찾는 것과 같은 검색 문제에 대한 수학적 레시피로, 무작위성의 이점을 활용할 수 있고 높은 확률로 매번 동일한 답을 생성할 수 있습니다. 그들은 레시피에서 무작위 비트의 효율성을 사용할 것이며 결과에서 무작위화 해제되어 결정론적으로 나타납니다.

연구원들은 그 이후로 유사 결정론적 알고리즘을 탐구해 왔습니다. 2017년, University of Warwick의 Santhanam과 Igor Oliveira(신작 작업에도 기여) 기술 된 임의성을 사용하고 확실하게 결정론적으로 보였지만 지수보다 빠르지만 다항식 시간보다 느린 "하위 지수" 시간에서 작동하는 소수를 구성하는 유사 결정론적 접근 방식입니다. 그리고 2021년에는 Tell and 리지에 첸, 캘리포니아 대학교 버클리 캠퍼스의 컴퓨터 과학자, 탐험 한 어려운 문제를 사용하여 의사 난수 생성기(무작위 출력과 구별할 수 없는 일련의 숫자를 생성하는 알고리즘)를 구축하는 방법. Chen은 "[우리는] 경도와 유사 무작위성 사이의 새로운 연관성을 발견했습니다."라고 말했습니다.

그 조각들은 마침내 2023년 봄에 모였습니다. 계산 복잡성에 대한 부트캠프 Berkeley의 Simons Institute for the Theory of Computing에서 연구원들이 문제에 대해 함께 작업하기 시작하여 과거 결과를 함께 짜기 시작했습니다. 새로운 작업을 위해 옥스포드의 컴퓨터 과학자이자 공동 저자인 Hanlin Ren은 새로운 방식으로 Chen-Tell 결과와 Santhanam-Oliveira 접근 방식을 결합하는 초기 아이디어를 가지고 있었다고 Chen은 말했습니다. 그런 다음 팀 전체가 아이디어를 더욱 완벽하게 개발하여 새 논문을 작성했습니다.

결과 의사 결정론적 알고리즘은 다항식 시간에 소수를 생성하기 위해 과거 작업을 보는 새로운 방법을 사용했다고 Santhanam은 말했습니다. 그것은 특정 길이의 소수를 출력하기 위해 무작위성을 사용했으며 도구는 무작위 추측보다 정확하고 결정론적 크런칭보다 계산적으로 효율적입니다.

새 알고리즘은 또한 놀라울 정도로 간단하며 광범위한 검색 문제에 적용할 수 있다고 Santhanam은 말했습니다. 실제로는 다항식 시간에서 구성원이 결정될 수 있는 소수와 같은 숫자의 밀집된 하위 집합에 적용될 수 있습니다. 하지만 완벽하지는 않습니다. 이 알고리즘은 무한히 많은 입력 길이에 대해 작동하지만 모든 자릿수 길이를 포함하지는 않습니다. 여전히 일부 값이 있을 수 있습니다. n 알고리즘이 결정론적으로 소수를 생성하지 않는 것입니다.

Grossman은 "그 작은 경고를 없애는 것이 좋을 것"이라고 말했습니다.

궁극적인 목표는 무작위성이 전혀 필요하지 않은 알고리즘을 찾는 것이라고 Santhanam은 말했습니다. 그러나 그 탐구는 열려 있습니다. "결정론은 우리가 사용하고 싶은 것"이라고 그는 말했습니다.

그러나 그는 의사 무작위 프로세스가 강력한 도구이며 소수 구성과 같은 프로젝트는 수학, 컴퓨터 과학, 정보 이론 및 기타 영역의 아이디어를 연결하는 데 사용하는 한 가지 방법일 뿐이라고 지적했습니다.

Tell은 “이러한 훌륭한 관찰 결과가 어디로 이어질지 생각하고 시도하는 것은 신나는 일입니다.”라고 말했습니다.