U-Bit Collapse in Arnault Composites:Probing the Boundary of Strong Lucas Pseudoprimes

기술 요약: Arnault 복합수에서의 U-비트 붕괴 (U-Bit Collapse in Arnault Composites)

문제 정의
밀러-라빈(Miller–Rabin) 테스트와 강력한 루카스(Lucas) 확률적 소수 테스트를 결합한 베일리-PSW(Baillie–PSW) 소수 판별법은 1980년 이후 광범위한 탐색에도 불구하고 알려진 합성수 반례가 없다. F. Arnault는 특정 소인수 분해를 설계(카마이클 수)하여 여러 밀러-라빈 테스트를 통과하는 합성 정수를 구성하는 프레임워크를 개발했으나, 이러한 구성 방식이 루카스 성분을 회피하도록 확장될 수 있는지 여부는 여전히 미해결 과제로 남아 있다. 본 논문은 Arnault 유형의 합성수, 특히 베이스 11까지의 밀러-라빈 테스트를 통과하도록 설계된 합성수가 루카스 수열에서 바일리-PSW 의사소수(pseudoprime)의 구축 경로를 시사할 만한 측정 가능한 "퇴화(degeneracy)"를 보이는지 조사한다.

방법론
본 연구는 약 350비트 크기의 합성수 $n = p_1 p_2 p_3$를 생성하기 위해 고처리량 구성 프로세스를 활용하였다. 구성 방식은 Arnault 프레임워크를 준수하였으며, 이를 통해 $p_i - 1$이 큰 공약수 $f$를 공유하여 해당 합성수가 베이스 11까지의 밀러-라빈 테스트를 통과하도록 보장하였다.

• 생성 규모: 프로세스는 단일 코어 ARM 인스턴스에서 실행되었으며, 분당 약 7,700개의 카마이클 수를 생성하였다.
• 선택 기준: 이 스트림으로부터 베이스 11까지의 모든 밀러-라빈 테스트를 통ผ่าน하는 합성수를 추출하였으며, 수율은 약 0.015%(시간당 약 20개)였다.
• 데이터셋: 상세 분석을 위해 총 200개의 합성수를 수집하였다.
• 테스트: 각 합성수는 표준 판별식 $D$ ( $(D/n) = -1$ 을 만족하도록 선택됨)를 사용하는 강력한 루카스 확률적 소수 테스트를 거쳤다.
• 지표: 저자들은 $n+1 = d \cdot 2^s$ 일 때, $\delta = \log_2 n - \log_2(U_d \mod n)$로 정의되는 **U-비트 붕괴 지표(U-bit collapse metric)**를 도입하였다. 이 지표는 루카스 항 $U_d$가 $[0, n)$ 범위에서 균등 분포로부터 벗어난 정도를 정량화한다. 유의미한 붕괴(큰 $\delta$ 값)는 루카스 항이 비정상적으로 작음을 나타내며, 이는 강력한 루카스 의사소수의 필요 조건이다.

주요 결과
200개의 샘플 데이터셋에 대한 분석 결과는 다음과 같다:

• 루카스 테스트 회피 실패: 200개의 샘플 모두 강력한 루카스 테스트를 통과하지 못했다. 즉, 강력한 루카스 의사소수는 발견되지 않았다.
• 미미한 U-비트 붕계: 관찰된 붕괴 값은 진정한 의사소수에 필요한 약 350비트의 감소량에 비해 매우 미미했다.
  • 평균 $\delta$: 1.61 비트.
  • 중앙값 $\delta$: 1.0 비트.
  • 최대 $\delta$: 8 비트 (344비트 합성수에서 관찰되었으며, 이는 336비트로의 감소를 의미함).
  • 제로 붕괴 (Zero Collapse): 26%의 샘플(52개 합성수)은 측정 가능한 붕괴를 보이지 않았으며($\delta = 0$), 이는 $U_d \mod n$ 값이 $[0, n)$ 내의 무작위 원소와 통계적으로 구별 불가능함을 의미한다.
• 매개변수 독립성: 상관관계 분석 결과, U-비트 붕괴와 Arnault 구성 매개변수($k, M$) 또는 합성수 비트 크기 사이의 관계는 무시할 수 있는 수준이었다 ($|\rho| < 0.09$).
• 잔여 패턴: 소인수들 사이에서 특정 모듈로 35의 잔여 클래스(예: 2, 8, 18, 22, 23, 32)가 빈번하게 나타났으나, 단일 패턴이 데이터셋을 지배하지 않았으며, 이러한 패턴이 루카스 저항성과 상관관계를 갖지는 않았다.

의의 및 주장
본 논문은 베이스 11까지의 밀러-라빈 테스트를 회피하도록 설계된 대수적 조건이 루카스 테스트를 회피하는 데 있어 유의미한 진전을 제공하지 못한다고 결론짓는다. 저자들은 밀러-라빈 테스트와 루카스 테스트가 근본적으로 독립적인 대수적 구조를 목표로 한다는 점을 주장한다.

• 직교성 (Orthogonality): 본 결과는 밀러-라빈과 루카스 테스트의 직교성에 대한 강력한 경험적 증거를 제공한다. 밀러-라빈 테스트를 깨기 위해 사용된 구성 방법론이 루카스 테스트를 깨는 부산물을 만들어내지는 않는다.
• Baillie–PSW의 견고성: 밀러-라빈을 저항하도록 특별히 설계된 합성수들을 높은 볼륨으로 샘로했음에도 불구하고 유의미한 U-비트 붕괴가 관찰되지 않았다는 점은 Baillie–PSW 테스트의 지속적인 신뢰성을 강화한다.
• 구성적 함의: 본 연구는 밀러-라빈 테스트를 통과하는 카마이클 또는 Arnault 구성에서 발견되는 것과는 질적으로 다른 대수적 제약 조건을 충족해야만 Baillie–PSW 의사소수를 구성할 수 있음을 시사한다. 저자들은 관찰된 최소한의 붕괴가 현재의 구성 패러다임이 가진 근본적인 한계를 반영하는 것이라고 상정한다.

결론
본 계산 연구는 Arnault 프레임워크가 밀러-라빈 의사소수를 생성하는 데는 효과적이지만, Baillie–PSW 테스트에 도전할 만큼 필요한 루카스 수열의 퇴화를 생성하는 데는 실패한다는 것을 입증한다. U-비트 붕괴 지표의 도입은 향후 조사를 위한 정량적 틀을 제공하지만, 데이터는 기존의 Arnault 패러다임을 넘어서는 대안적인 구성 방법이 Baillie–PSW 반례 문제를 해결하기 위해 필요할 수 있음을 시사한다.