Tag Archives: primes

50 Awesome facts about prime numbers

A prime is a natural number greater than one whose only factors are one and itself. I find primes pretty cool, so I made a list of 50 facts about primes: The first twenty primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, […]

Effectiveness of the Miller-Rabin primality test

Last time, I explained the Miller-Rabin probabilistic primality test. Let's recall it: Theorem. Let $p$ be an odd prime and write $p-1 = 2^kq$ where $q$ is an odd number. If $a$ is relatively prime to $p$ then at least one of the following statements is true: $a^q\equiv 1\pmod{p}$, or One of $a^q,a^{2q},a^{4q},\dots,a^{2^{k-1}q}$ is congruent […]