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