Documention for: prime.r Created by: tomc on: 18-Oct-2005 Format: text/editable Downloaded on: 27-Sep-2020 this algo is built around "Fermat's little theorem" see: http://en.wikipedia.org/wiki/Fermat%27s_little_theorem more specifically an implementation of FLT, the lucas-lehmer (non)primality test which states if 2^(p-1) // p != 1 then p IS composite. note well!!! 2^(p-1) // p == 1 does NOT gaurentee p is prime but does allow it may be prime (called a probable prime or pseudoprime) the larger the number being tested the larger the chance of a non-prime returning 1 this can be offset by doing more tests with base > 2 as indicated by FLT see: http://en.wikipedia.org/wiki/Lucas-Lehmer_primality_test so the lucas-lehmer test requires power and modulas power is repeated multiplacation of the same number multiplication of the same number is repeated addition of the same number adding of the same number is doubling doubling in binary is left shifting modulas is division division is repeated subtraction of the same number halving in binary is right shifting furthermore, before the current common multiplication algo existed there was a form of myltiplying a b involved only doubling a and having b see: "http://en.wikipedia.org/wiki/Egyptian_multiplication note: the same concept used for "Egyptian_multiplication" can be extended to exponentiation. the last part needed is the understanding: for addition,subtraction & multiplication modulo at the end, is no different than modulo every step of the way. see: http://en.wikipedia.org/wiki/Modular_arithmetic but modulo every step of the way means less work overall because the numbers you are working with can never get more than twice the size of the modulas. (a + b) // m == ((a // m) + (b // m)) // m (a // m) + (b // m) < m + m a number O(2^(2^30)) is a staggeringly huge number to repeatedly subtract O(2^30) from it to find the remainder would take a very long time (if it could even be representated in binary). But keeping all the parts O(2^31) by applying mod O(2^30) means it is just a handful of operations to arrive at the same conclusion "if you don't make no trouble, there won't be no trouble"