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