머리부터 온몸이 무너져내리는 기분이다. 망연자실이란 게 이런 상황이란 것 아닌가. 지독한 가난과 외로움도 나의 눈을 가리면 느끼지 않을 수는 없을까. 남의 행복이 나의 불행은 확실한 것 같다. 무언가 잘못되고 있다는 기사만 자꾸 읽게 되는 것은 내가 심보가 고약한 것일까.
앞에서 썼던 기사를 실제 적용하면 얼마나 유용한지 적용해보자.
먼 지수 분해 가설은 차치하고 여기서는 페르마 소정리와 페퓨닛수 기반 소수 판별을 결합한 하이브리드법을 실제 어떻게 적용할지 적어본다.
먼저 소수인지 아닌지를 판별할 수보다 1작은 수를 지수로한 2의 N제곱-1을 나누어본다.
가령 7이 소수인지 아닌지 확인하고자하면 2의 6제곱-1을 7로 나누어보는 것이다. 나누어떨어진다. 소수일 가능성이 매우 높다. 그러나 341의 경우는 2의 340제곱-1을 나누어떨어뜨려 소수로 오해할 수 있다.
그래서 그 다음으로 적용하는 것이 소수인지 아닌지 확인하고자하는 수보다 1작은 수의 자릿수의 1로만 구성된, 레퓨닛수를 나누어본다.
1이 6자린인 111,111은 7로 나누었을때 나누어 떨어지는 것이다. 앞의 적용방법과 두번째 적용방법까지 모두 통과했으니 소수가 확실하다고 말할 수 있다.
그러나 341은 앞의 방법을 통과했지만, 340자릿수의 레퓨닛수를 나누어 떨어뜨리지 못한다. 합성수이다.
즉 강동진 소수판별 모델은 이 두가지 테스트에서 모두 통과된 수만이 소수로 판별한다는 것을 말한다.
다음은 챗GPT가 리라이팅해준 글이다.
“한 번 속아도, 두 번은 못 속인다” — 강동진 하이브리드 소수 판별 모델
지금까지의 소수 판별은 대개 어렵고 복잡했다.
어떤 방법은 빠르지만 반례가 존재했고, 어떤 방법은 정확하지만 계산량이 지나치게 컸다.
필자가 제안하는 방식은 다르다.
복잡한 이론을 늘어놓기보다, 서로 다른 두 검증을 연속으로 통과해야만 소수로 인정하는 구조다.
핵심은 단순하다.
첫 번째 관문은 페르마 소정리 기반 검증,
두 번째 관문은 레퓨닛수 기반 검증이다.
그리고 이 두 검증을 모두 통과한 수만을 소수로 인정한다.
첫 번째 관문 — “2의 거듭제곱 검증”
먼저 어떤 수 N이 소수인지 확인하고 싶다면,
N보다 1 작은 수를 지수로 하는 다음 값을 만든다.
2
N−1
−1
그리고 이것을 N으로 나누어본다.
예를 들어 7을 검사한다고 하자.
2
6
−1=63
63은 7로 정확히 나누어진다.
즉 첫 번째 검증을 통과한다.
이는 페르마 소정리와 연결된다.
소수라면 대체로 이런 성질을 만족하기 때문이다.
하지만 문제는 여기서 끝나지 않는다.
페르마 소정리의 함정
합성수인데도 첫 번째 검증을 통과하는 수가 존재한다.
대표적인 수가 341이다.
2
340
−1
이 수는 341로 나누어떨어진다.
겉보기에는 소수처럼 행동한다.
그러나 실제로는
341=11×31
인 합성수다.
즉 페르마 기반 검증 하나만으로는 완전하지 않다.
바로 이 지점에서 두 번째 관문이 등장한다.
두 번째 관문 — 레퓨닛수 검증
이제 같은 수 N에 대해,
N보다 1 작은 자리수를 가지는 레퓨닛수를 만든다.
레퓨닛수란 숫자 1만 반복된 수를 의미한다.
7을 다시 예로 들어보자.
7보다 1 작은 수는 6이다.
따라서 6자리 레퓨닛수를 만든다.
111111
이 수는 7로 정확히 나누어진다.
즉 7은
첫 번째 검증 통과
두 번째 검증 통과
를 모두 만족한다.
따라서 소수로 판별된다.
341에 적용하면 어떻게 되는가
341 역시 첫 번째 검증은 통과했다.
바로 이것이 기존 방식의 약점이었다.
그러나 두 번째 검증에서 무너진다.
340자리 레퓨닛수는 341로 나누어떨어지지 않는다.
즉 341은
페르마 기반 검증은 통과
레퓨닛 기반 검증은 실패
라는 결과가 나온다.
결국 합성수라는 정체가 드러난다.
핵심은 “이중 검증”이다
강동진 소수 판별 모델의 핵심은 단순하다.
첫 번째 시험에서 속일 수는 있어도,
두 번째 시험까지 동시에 속이기는 훨씬 어렵다는 것이다.
즉 이 모델은 단순히 “한 가지 성질”에 기대지 않는다.
거듭제곱 기반 구조
순환마디와 레퓨닛 기반 구조
라는 서로 다른 두 체계를 동시에 요구한다.
하나는 통과해도,
둘을 동시에 만족하지 못하면 탈락이다.
기존 판별법과 다른 점
기존의 단순 페르마 검사는 빠르지만 위장 합성수에 취약했다.
반면 강동진 모델은 그 뒤에 레퓨닛 검증을 추가한다.
즉,
“거듭제곱 구조”와
“순환 구조”
를 동시에 확인하는 셈이다.
이 방식은 단순한 계산 규칙의 조합 같아 보이지만, 실제로는 서로 다른 수론 구조를 교차 검증한다는 점에서 의미가 있다.
결론
소수는 수학의 원자라 불린다.
그러나 지금까지 그 원자를 가려내는 작업은 지나치게 복잡하거나, 반대로 허점이 존재했다.
강동진 하이브리드 모델은 단순한 질문을 던진다.
“한 번의 시험으로 부족하다면,
왜 두 번 시험하지 않는가?”
페르마 검사를 통과하고,
레퓨닛 검사를 다시 통과한 수만 소수로 인정한다.
이 구조는 단순하지만 강하다.
그리고 적어도 341 같은 위장 합성수는,
두 번째 관문에서 더 이상 숨을 수 없다.
페르마 소정리와 레퓨닛 수 기반 소수판별법의 두 테스트 통과시 소수로 판별','https://www.h-money.co.kr/news_view.jsp?ncd=58231','https://www.h-money.co.kr/news/upload/1778211672817_c.png','머리부터 온몸이 무너져내리는 기분이다. 망연자실이란 게 이런 상황이란 것 아닌가. 지독한 가난과 외로움도 나의 눈을 가리면 느끼지 않을 수는 없을까. 남의 행복이 나의 불행은 확실한 것 같다. 무언가 …');)
