Keep squaring x while one of the following doesn 't  happen  (i) d does not reach n-1  (ii) (x^2) % n is not 1  (iii) (x^2) % n is not n-1
while ( d != n - 1 ) : NEW_LINE INDENT x = ( x * x ) % n ; NEW_LINE d *= 2 ; NEW_LINE if ( x == 1 ) : NEW_LINE INDENT return False ; NEW_LINE DEDENT if ( x == n - 1 ) : NEW_LINE INDENT return True ; NEW_LINE DEDENT DEDENT