Logo PTI Logo FedCSIS

Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 43

A statistical hypothesis test for primality based on random divisor sampling: Principles, properties, adaptive design, and algorithmic analysis

DOI: http://dx.doi.org/10.15439/2025F0998

Citation: Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 43, pages 795–800 ()

Full text

Abstract. We propose a statistical hypothesis test for determining whether a given integer $n \geq 2$ is prime. Under the null hypothesis $H\_0$, we assume that $n$ is not a prime (i.e., composite). The test operates by randomly sampling integers from the candidate divisor set $\mathcal{D} = \{2, 3, \ldots, \lfloor \sqrt{n} \rfloor\}$ and checking whether any of them divide $n$. If a proper divisor is found, $H\_0$ is not rejected and $n$ is declared composite. If no divisor is found among an initial set of $k\_0$ samples, additional $k$ samples are drawn, and a $p$-value is computed based on the probability of missing all actual divisors under $H\_0$. 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 $H\_0$ at a given significance level $\alpha$ under the conservative assumption of only one true divisor ($m = 1$). The algorithm has worst-case time complexity $\mathcal{O}(\sqrt{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.

References

  1. R. L. Rivest, A. Shamir, and L. Adleman. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. In: Communications of the ACM 21.2 (1978), pp. 120–126. DOI:10.1145/359340.359342.
  2. R. Crandall and C. Pomerance. Prime Numbers: A Computational Perspective. 2nd. Springer, 2005. ISBN: 9780387252820. DOI: 10.1017/S0025557200182932.
  3. G. L. Miller. “Riemann’s Hypothesis and Tests for Primality”. In: Journal of Computer and System Sciences 13.3 (1976), pp. 300–317. DOI: 10.1016/S0022-0000(76)80043-8.
  4. K. H. Rosen. Elementary Number Theory and Its Applications. 6th. Addison-Wesley, 2011. ISBN: 9780321500311.
  5. M. O. Rabin. “Probabilistic Algorithm for Testing Primality”. In: Journal of Number Theory 12.1 (1980), pp. 128–138. DOI:10.1016/0022-314X(80)90084-0.
  6. M. Agrawal, N. Kayal, and N. Saxena. “PRIMES is in P”. In: Annals of Mathematics 160.2 (2004), pp. 781–793. DOI: 10.4007/annals.2004.160.781.
  7. G. Casella and R. L. Berger. Statistical Inference. 2nd. Duxbury Press, 2002. ISBN : 9780534243128. DOI: 10.1201/9781003456285.