Is there any simple primality test for large integer for students in the high school level?

Question

In high school the standard primality test of an integer $n$ is to find a square root of this integer then test divisibility of $n$ with primes less than the integer part of $\sqrt{n}$ but this method is difficult to do by hand for large number then , Is there any simple primality test for large integer for students in the high school level for example $12109$?

Answer 1

Write $n-1 = 2^sd$ where $d$ is odd and $s$ is non-negative:

• $n$ is a strong probable-prime base $a$ (an $a$-SPRP) if either $a^d \equiv 1 \pmod n$ or $(a^d)^{2r} \equiv -1 \pmod n$ for some non-negative $r$ less than $s$.

For large integers for a human but small for number theory, this website lists limits values for the first primes sprp tests.

https://primes.utm.edu/prove/prove2_3.html

e.g. for $n<1\,373\,653$ then $\{2,3\}$-SPRP is sufficient.

This paper http://ceur-ws.org/Vol-1326/020-Forisek.pdf

suggests that for integers $n<2^{32}$ we can improve the $\{2,3,5,7,11\}$-SPRP test from the former website by performing a $\{2,7,61\}-SPRP$ test instead.