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"