Choose an integer value for a such that 2 ≤ a ≤ n - 1. If an (mod n) = a (mod n), then n is likely prime. If this is not true, n is not prime. Repeat with different values of a to increase confidence in primality
Find values for s and d such that n−1=2s∗d{\displaystyle n-1=2^{s}*d}. Choose an integer value for a such that 2 ≤ a ≤ n - 1. If ad = +1 (mod n) or -1 (mod n), then n is probably prime. Skip to test result. Otherwise, go to next step. Square your answer (a2d{\displaystyle a^{2d}}). If this equals -1 (mod n), then n is probably prime. Skip to test result. Otherwise repeat (a4d{\displaystyle a^{4d}} etc. ) until a2s−1d{\displaystyle a^{2^{s-1}d}}. If you ever square a number which is not ±1{\displaystyle \pm 1} (mod n) and end up with +1 (mod n), then n is not prime. If a2s−1d≠±1{\displaystyle a^{2^{s-1}d}\neq \pm 1} (mod n), then n is not prime. Test result: If n passes test, repeat with different values of a to increase confidence.
Floor(x) rounds x to the closest integer ≤ x.
Many calculators have a mod button, but see the end of this section for how to solve this by hand for large numbers.
Rewrite the expression with more manageable exponents: (325∗325){\displaystyle (3^{25}*3^{25})} mod 50. (You may need to break it down further if calculating by hand). (325∗325){\displaystyle (3^{25}*3^{25})} mod 50 = (325{\displaystyle (3^{25}} mod 50 ∗325{\displaystyle *3^{25}} mod 50) mod 50. (This is a property of modular multiplication. ) 325{\displaystyle 3^{25}} mod 50 = 43. (325{\displaystyle (3^{25}} mod 50 ∗325{\displaystyle 3^{25}} mod 50) mod 50 = (43∗43){\displaystyle (4343)} mod 50 =1849{\displaystyle =1849} mod 50 =49{\displaystyle =49}
“Prime1” = 35 Prime2 = 97
Data1 = 1 Data2 = 2
Calculate MMI MMI1 = Prime2 ^ -1 Mod Prime1 MMI2 = Prime1 ^ -1 Mod Prime2 For Prime Numbers only (it will give a number for non-prime numbers but it won’t be its MMI): MMI1 = (Prime2 ^ (Prime1-2)) % Prime1 MMI2 = (Prime1 ^ (Prime2-2)) % Prime2 e. g MMI1 = (97 ^ 33) % 35 MMI2 = (35 ^ 95) % 97
For MMI1 F(1) = Prime2 % Prime1 = 97 % 35 = 27 F(2) = F(1) * F(1) % Prime1 = 27 * 27 % 35 = 29 F(4) = F(2) * F(2) % Prime1 = 29 * 29 % 35 = 1 F(8) = F(4) * F(4) % Prime1 = 1 * 1 % 35 = 1 F(16) =F(8) * F(8) % Prime1 = 1 * 1 % 35 = 1 F(32) =F(16) * F(16) % Prime1 = 1 * 1 % 35 = 1 Calculate the binary of Prime1 - 2 35 -2 = 33 (10001) base 2 MMI1 = F(33) = F(32) * F(1) mod 35 MMI1 = F(33) = 1 * 27 Mod 35 MMI1 = 27 For MMI2 F(1) = Prime1 % Prime2 = 35 % 97 = 35 F(2) = F(1) * F(1) % Prime2 = 35 * 35 mod 97 = 61 F(4) = F(2) * F(2) % Prime2 = 61 * 61 mod 97 = 35 F(8) = F(4) * F(4) % Prime2 = 35 * 35 mod 97 = 61 F(16) = F(8) * F(8) % Prime2 = 61 * 61 mod 97 = 35 F(32) = F(16) * F(16) % Prime2 = 35 * 35 mod 97 = 61 F(64) = F(32) * F(32) % Prime2 = 61 * 61 mod 97 = 35 F(128) = F(64) * F(64) % Prime2 = 35 * 35 mod 97 = 61 Calculate the binary of Prime2 - 2 97 - 2 = 95 = (1011111) base 2 MMI2 = (((((F(64) * F(16) % 97) * F(8) % 97) * F(4) % 97) * F(2) % 97) * F(1) % 97) MMI2 = (((((35 * 35) %97) * 61) % 97) * 35 % 97) * 61 % 97) * 35 % 97) MMI2 = 61
Answer = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35) Answer = (2619 + 4270) % 3395 Answer = 99
Calculate (Answer - Data1) % Prime1 99 -1 % 35 = 28 Since 28 is greater than 0, 35 is not prime
Calculate (Answer - Data2) % Prime2 99 - 2 % 97 = 0 Since 0 equals 0, 97 is potentially prime
If step 7 is 0: Use a different “prime1” where prime1 is a non-prime Use a different prime 1 where prime 1 is an actual prime. In this case, steps 6 and 7 should equal 0. Use different data points for data1 and data2. If step 7 is 0 every time, there is an extremely high probability that prime2 is prime. Steps 1 though 7 are known to fail in certain cases when the first number is a non-prime number and the second prime is a factor of the non-prime number “prime1”. It works in all scenarios where both numbers are prime. The reason why steps 1 though 7 are repeated is because there are a few scenarios where, even if prime1 is not prime and prime2 is not prime, step 7 still works out to be zero, for one or both the numbers. These circumstances are rare. By changing prime1 to a different non-prime number, if prime2 is not prime, prime2 will rapidly not equal zero in step 7. Except for the instance where “prime1” is a factor of prime2, prime numbers will always equal zero in step 7.
