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 ) { $ x = ( $ x * $ x ) % $ n ; $ d *= 2 ; if ( $ x == 1 ) return false ; if ( $ x == $ n - 1 ) return true ; }