현재까지 발견된 가장 큰 소수 - (2024년 10월)

 

현재까지 발견된 가장 큰 소수(2024년 10월 12일 발견)

 

2024년 10월 12일에 새로운 소수가 발견되었다.
$$2^{136,279,841}-1$$
10진수로 표기하면 41,024,320자리 숫자이다. 이 숫자는 루크 듀런트가 GIMPS(Great Internet Mersenne Prime Search)에 자원한 컴퓨터에 의해 2024년 10월 12일에 발견되었다. 

그 이전에 발견된 최대 소수는 $2^{82,589,933}-1$이었다. 이 수는 24,862,048자리였다. 무려 6년만에 기록을 갈아치우게 된 것이다. 

 

이처럼  $2^{n}-1$($n$은 자연수)와 같은 형식으로 표현하는 소수를 메르센 소수라고 한다. 메르센 소수들은 다른 일반적인 소수들에 비해 소수인지 아닌지 더 빠르게 판별할 수 있다. 특히 메르센 소수는 $2^{n}-1$이기 때문에 이를 2진법의 숫자로 표현하면 1을 $n$개 쓰면 된다. 

 

${n}$이 소수인지 확인하기 위해서는 2부터 ${\sqrt{n}}$​까지만 나눗셈을 수행해서 나머지가 있는지 나누어 떨어지는지 확인하면 된다. $a \times b = n$이라면, $ a $ 또는 $ b $ 중 하나는 ${\sqrt{n}}$​ 이하이기 때문이다. 따라서 소수인지 아닌지 판별하는 방법은 아래와 같은 알고리즘으로 가능하다. 파이썬 코드도 첨부하였다. 

 

1. $n$이 $2$ 미만이면 소수가 아님.

2. $n=2$ 또는 $n=3$ 이면 소수.

3. $n$이 짝수 또는 3의 배수라면 소수가 아님.

4. $5$부터 $\sqrt{n}$ ​까지 홀수만 나눠서 나누어 떨어지는지 확인

 

import math
def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(n)) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

 

더 큰 소수를 찾는 것이 더 강력한 암호화를 허용하는 것으로 널리 알려져 있지만 이는 잘못된 것이라고 한다.

연도에 따른 최대 소수의 발견

By Nicoguaro - 자작, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=51383347

File:Digits in largest prime found as a function of time.svg - Wikimedia Commons