• + 0 comments

    Some hints if you are stuck:

    For any fixed N, there exists a set of witnesses such that Miller-Rabin with those fixed bases will correctly identify all composite numbers less than N. This removes the element of randomness from Miller-Rabin, and the set of fixed bases is actually surprisingly small for N = 2^64.

    If N^(1/3) < x < N and x is not divisible by any prime < N^(1/3), then x is the product of either one or two primes larger than N^(2/3). In either case, you don't need to factor it completely. If x is a square, how many distinct prime divisors does it have? And how many divisors total? If x is not a square, how many divisors does it have? And how many divisors total?