::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:
function SPRP:  Strong Probable Prime test.

 entry N     word,         &Unsigned odd number to test
       B     word          :Base to test against

  exit Sprp  Bit           :0 - Proven composite; 1 - Likely prime; maybe not

 local Z     byte,         &Number of zero bits on the right side of D
       D     word,         &N - 1; right justified
       R     word,         &Residual
       Nc    cell          :N in 64 bits

precondition
   N // 1  fault  N;          FAULT:  Cannot test 0 or 1 for primality.
   N /\ 1  fault  N|d#;       FAULT:  Cannot test even numbers for primality.
.
:...............................................................................


: Find D and Z that satisfy N - 1 = D * 2^Z, where D is odd and Z >= 0.
:
D = (N - 1) // 1;                      Always remove the rightmost zero.

DO until  D /\ 1:                      DO until N - 1 is right justified,
   D //= 1
   Z  += 1;                               Count the zero bits.
-

R = Power.Mod( B, D, N );              B ^ D mod N

IF R _> 1  and  R ~= N - 1:             IF R is not 0, 1, nor N - 1,
   : See if B^(2^R) mod N = N - 1, where 0 <= R < Z.
   :
   Nc = positive{ N };                    Zero extend N to 64 bits.

   DO positive{ Z }  times:               DO over each zero bit,
      R = cell{ positive( R _* R ) % Nc };   R^2 mod N

      IF R = N - 1:                          IF prime or a strong psuedo prime,
         Sprp = 1;                              Not known to be composite
   UNDO;                                  UNDO
   -  .
ELSE IF R  or  N _<= B:                 ELSE IF r = 1, N-1, or r = 0 and tiny N,
   Sprp = 1;                               Not known to be composite.
.

return