Documention for: prime.r
Created by: tomc
Downloaded on: 28-Jan-2020
this algo is built around "Fermat's little theorem"
more specifically an implementation of FLT, the lucas-lehmer (non)primality
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
this can be offset by doing more tests with base > 2 as indicated
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
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
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
but modulo every step of the way means less work overall because
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
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