Re: Time complexity

"Paul Hosre" <reallyfyne@xxxxxxxx> wrote in message
news:1169562269.885455.240980@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
A Simple question of time complexity to check if a given number is a
prime ?
Thanks

I'm not sure what level of detail you want.

Do you mean to factor the number or just verify it is prime?

If you want to verify that it is prime to a reasonable level of certainty,
you can use something like this:

http://en.wikipedia.org/wiki/Miller-Rabin_primality_test

I believe the compute complexity has the effect of the growing operands
built-in, i.e.

<BEGIN>
Using modular exponentiation by repeated squaring, the running time of this
algorithm is O(k × log3 n), where k is the number of different values of a
we test; thus this is an efficient, polynomial-time algorithm. FFT-based
multiplication can push the running time down to Õ(k × log2 n).
<END>

It would have a different compute complexity if the integers you are
interested in are supported directly by the machine.

I'm not sure how much it costs to actually factor a number.

Dave.


.

Quantcast