More efficient Rabin-Miller test: with random witnesses, skip redundant