Is a Primality test Using Wilson's Linear?

Question

I think we require $n-1$ multiplications, after each of which we are allowed perform a $mod n$ operation, thus not blowing up in memory. We may finish earlier but maximally $2(n-1)$ calculations are required.

Is this correct?

Answer 1

Algorithmic complexity is normally measured in terms of the size of the input, i.e. the amount of memory it takes to store. For primality testing -- or anything where the input is an integer -- this is the number of bits of the integer, i.e. roughly $\log_2 n$. In those terms, this algorithm is exponential.