20080615 10^20

괜찮은 알고리즘을 가지고 있을 때 1.6G클럭의 노트북으로도 (10진법으로)스무자리 이하의 모든 소수를 찾는 데 1주일이면 된다.
(t = cputime; A = primes(\(10^8\)); cputime-t ------- matlab. 내 노트북에서 6초 남짓.
자릿수의 증가가 곱하는 시간에 미치는 영향은 무시했으나 이것도 실제로 해보면 엄청날듯)

10비트를 대략 10의 3승으로 잡으면, 200비트는 10진법으로 대략 60자리 숫자다.
그럼 400비트는 120자리 숫자

소수 두개의 곱으로 이루어진 400비트의 수를 소인수분해하고 싶다면,
병렬연산이 가능하고 누군가 100억대의 컴퓨터를 동원할 수 있다 해도 - 이건 그리드나 혹은 수퍼컴퓨터로 비교적 간단(?)하게 해결할 수 있을 듯.
200비트 이하의 모든 소수 둘을 곱해보는 데 \(10^{30}\)주가 필요하다. -_-;
400비트 수가 소수의 제곱이 아닌 한 200비트 소수 하나는 다른 하나보다 클 것이므로 a*b(a>b)사례만 계산하면 위 시간이 반으로 줄고, 1년을 대략 50주 잡으면 저기서 0 두개를 뺀 년수(\(10^{28}\)년)만큼이 필요하다.
별로 도움이 안된다 -_-;;;

200비트 이하의 모든 소수를 찾아 곱해보는 방식 말고
범위를 정해서 비스무리 한 애들만 공략한다고 하면 - 이렇게 하면 소수 여부 모르는 채로 가능한 모든 수로 나눠야 하겠지만 - 400비트의 수가 운좋게도 정확히 200비트의 소수 두개의 곱이라고 해도 모든 60자리 숫자(59자리 등등은 제외하고, 짝수도 제외하고)로 나누어 보는 시간이 필요하다. 그런데 뭐 이것도 그닥 -_-;;;



도서관에서 책을 빌렸는데 그냥 재미있다. 이해는 뭐 하나도 안가는데 많은 사람들의 도전을 구경할 수 있어서.(에피소드들이 있는건 아니고 그냥 많은 사람들이 찾아낸 많은 숫자들만 가득하다 ㅋ)


6/15 21:16
*
추측이 완전히 틀렸군
n 이하의 소수 개수를 π(n) 이라 하면
지금까지 계산된 π(n)의 최대치는 2000년 10월 27일에 자비어 고든에 의해 계산되었는데
고작 π(1021)
*
 어떤사람이 Fermat(페르마 1607~1665)에게 100895598169가 소수인지 묻자 페르마는 곧바로 898423과 112303의 곱으로 나타낼 수 있는 합성수라고 대답했다. 페르마가 그 답을 어떻게 찾았는지는 아무도 모른다. 사람들은 페르마가 인수분해 비법을 알고 있었으나 이후에 그 방법이 유실되었다고 생각한다.