**Combinatorial Primality Test **

*Maheswara Rao Valluri*

**Abstract: **This paper provides proofs of the results of Laisant - Beaujeux: (1) If an integer of the form $n=4k+1$, $k>0$ is prime, then $\left(\begin{array}{c}n-1\\m\end{array}\right)\equiv1(mod\,n),m=\frac{n-1}{2}$, and (2) If an integer of the form $n=4k+3$, $k\geq0$ is prime, then $\left(\begin{array}{c}n-1\\m\end{array}\right)\equiv-1(mod\,n),m=\frac{n-1}{2}$. In addition, the author proposes important conjectures based on the converse of the above theorems which aim to establish primality
of $n$. These conjectures are scrutinized by the given combinatorial primality test algorithm which can also distinguish patterns of prime $n$ whether it is of the form $4k+1$ or $4k+3$.

**Category / Keywords: **Combinatorial pseudoprimes, Integer factorization problem, Primality

**Date: **received 7 Feb 2019, last revised 9 Feb 2019

**Contact author: **maheswara valluri at fnu ac fj

**Available format(s): **PDF | BibTeX Citation

**Version: **20190213:034520 (All versions of this report)

**Short URL: **ia.cr/2019/125

[ Cryptology ePrint archive ]