Script Library: 1225 scripts

# Documentation for: prime.r

```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:

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
```