저는 Linux Mint 21.2를 사용하고 있으며 제 컴퓨터는 Intel Core i-7 6700 3.4GHZ입니다.
Python으로 소수성 테스트를 작성하고 많은 데이터를 가지고 확인해봤습니다.
많은 테스트와 마찬가지로 Fermat의 변형이므로 모듈러 지수화를 수행했습니다 powmod(3, n-1, n).
나는 그것이 n = k * 2^k+1소수임을 증명할 수 있다 k = 6679881. 이는 소수임이 입증되었기 때문에 놀라운 일이 아닙니다. 내 테스트에서는 이 2.010.852자리 숫자를 완성하는 데 124시간이 걸렸습니다.
n = 2^(2^k)+1이제 에 포함된 페르마의 숫자 F_33을 확인하고 싶습니다 k = 33. 이 숫자는 약 2.500.000자리입니다.
실행하면 몇 분 후에 다음 오류가 발생합니다.
NU MP: Cannot allocate memory (size=549755818000)
bash: line 1: 19354 Aborted
(core dumped)
나에게 이 시험을 볼 기회가 있나요?
답변1
512GB RAM을 사용하려고 합니다. 프로그램을 최적화하거나 서버를 임대하십시오.
교환하는 것이 도움이 될 수 없다고 생각합니다.
답변2
계속할 수 있다고 해도 결과를 보기가 거의 불가능합니다. 왜냐하면 이 오류는 메모리가 부족하다는 것을 알려주기 때문입니다.
내가 엔딩을 절대 볼 수 없다고 말하는 이유는 다음과 같습니다.
복잡성을 비교해 보겠습니다.
n = k * 2^k+1은 k = 6679881의 소수입니다.
6,679,881은 약 2²³(실제로 안전한 상한선)이므로 n≒2 2²³+ 6679881 ≒ 2 2²³ 입니다.
n = 2^(2^k)+1 여기서 k = 33
이 문제가 몇 번이나 발생하는지 알아보기 위해 이전 n의 대략적인 크기로 나누어 보겠습니다.
2233 / 2223 = 2233-223 ≒ 2233
즉, 더 큰 n에 대해 소수를 확인하는 것은 훨씬 더 복잡하여 기다리는 시간이 새로운 문제의 지수에 비해 중요하지 않거나 발생하지도 않습니다.