Primality Test | Set 3 ( Millerâ €“ Rabin ) | Utility function to do modular exponentiation . It returns ( x ^ y ) % p ; Initialize result ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now $y = $y >> 1 ; $y = $y / 2 ; This function is called for all k trials . It returns false if n is composite and returns false if n is probably prime . d is an odd number such that d * 2 < sup > r < / sup > = n - 1 for some r >= 1 ; Pick a random number in [ 2. . n - 2 ] Corner cases make sure that n > 4 ; Compute a ^ d % n ; 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 ; Return composite ; It returns false if n is composite and returns true if n is probably prime . k is an input parameter that determines accuracy level . Higher value of k indicates more accuracy . ; Corner cases ; Find r such that n = 2 ^ d * r + 1 for some r >= 1 ; Iterate given nber of ' k ' times ; Driver Code Number of iterations
< ? php function power ( $ x , $ y , $ p ) { $ res = 1 ; $ x = $ x % $ p ; while ( $ y > 0 ) { if ( $ y & 1 ) $ res = ( $ res * $ x ) % $ p ; $ x = ( $ x * $ x ) % $ p ; } return $ res ; } function miillerTest ( $ d , $ n ) { $ a = 2 + rand ( ) % ( $ n - 4 ) ; $ x = power ( $ a , $ d , $ n ) ; if ( $ x == 1 $ x == $ n - 1 ) return true ; while ( $ d != $ n - 1 ) { $ x = ( $ x * $ x ) % $ n ; $ d *= 2 ; if ( $ x == 1 ) return false ; if ( $ x == $ n - 1 ) return true ; } return false ; } function isPrime ( $ n , $ k ) { if ( $ n <= 1 $ n == 4 ) return false ; if ( $ n <= 3 ) return true ; $ d = $ n - 1 ; while ( $ d % 2 == 0 ) $ d /= 2 ; for ( $ i = 0 ; $ i < $ k ; $ i ++ ) if ( ! miillerTest ( $ d , $ n ) ) return false ; return true ; } $ k = 4 ; echo " All ▁ primes ▁ smaller ▁ than ▁ 100 : ▁ STRNEWLINE " ; for ( $ n = 1 ; $ n < 100 ; $ n ++ ) if ( isPrime ( $ n , $ k ) ) echo $ n , " ▁ " ; ? >