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$?
Asked
Active
Viewed 281 times
0
-
I think in all case it needs to work. – Michael Rozenberg Jan 22 '18 at 20:00
-
$\sqrt {12109}\approx 110$...not really all that hard to do by hand. Otherwise, Miller Rabin is probably the simplest. – lulu Jan 22 '18 at 20:08
-
Also the Pocklington primality test is nice. The example is done with $27457$. – Dietrich Burde Jan 22 '18 at 20:16
-
Another fairly easy test is Sieve of Eratosthenes ... it's a mechanical work. – rtybase Jan 22 '18 at 21:26
-
I don't think that students are expected to check such numbers by hand. Correct me, if I am wrong. A little better than trial division is the method also considering quadratic residues, for example, the given number can easily be detected to be the sum of two squares. It was such a method that was used to factor $2^{67}-1$ by hand, but it took the Sundays of three years (i right now do not remember who did this). – Peter Jan 23 '18 at 13:46
1 Answers
0
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.
