Given such an "a" (called a "witness") and the prime factorization of "n" − 1, it's simple to verify the above conditions quickly: we only need to do a linear number of modular exponentiations, since every integer has fewer prime factors than bits, and each of these can be done by exponentiation by squaring in O(log "n") multiplications (see big-O notation). Even with grade-school integer multiplication, this is only O((log "n")4) time; using the multiplication algorithm with best-known asymptotic running time, the Schönhage–Strassen algorithm, we can lower this to O((log "n")3(log log "n")(log log log "n")) time, or using soft-O notation Õ((log "n")3).