A statistical hypothesis test for primality based on random divisor sampling: Principles, properties, adaptive design, and algorithmic analysis
Lubomír Štěpánek · Annals of Computer Science and Information Systems · 2025
We propose a statistical hypothesis test for determining whether a given integer n ≥ 2 is prime.Under the null hypothesis H0, we assume that n is not a prime (i.e., composite).The test operates by randomly sampling integers from the candidate divisor set D = {2, 3, . . ., ⌊ √ n⌋} and checking whether any of them divide n.If a proper divisor is found, H0 is not rejected and n is declared composite.If no divisor is found among an initial set of k0 samples, additional k samples are drawn, and a p-value is computed based on the probability of missing all actual divisors under H0.This probability is calculated exactly via a hypergeometric distribution and approximated using an exponential bound.We derive a closed-form upper bound for the minimal number of trials k required to reject H0 at a given significance level α under the conservative assumption of only one true divisor (m = 1).The algorithm has worst-case time complexity O( √ n), matching that of classical trial division, but its expected runtime is substantially lower when n has multiple divisors.The proposed test is simple, statistically interpretable, and well-suited both as an educational tool and as a lightweight probabilistic pre-check in layered primality testing pipelines.