Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trial division Primality

  1. Oct 30, 2006 #1

    This is very simple, and obviously i'm missing something trivial, but I still don't get it.

    An algorithm is said to run in polynomial time if it runs in O(n^K) time.

    That's why dijkstra for example, who runs in O(V^2), runs in polynomial time.

    That said, my doubt is the following:
    If a brute-force trial division primality check algorithm, runs in O(n^(1/2)), why it isn't considered in polynomial time?

    Thanks beforehands,
  2. jcsd
  3. Oct 30, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The running time of an algorithm is usually expressed in terms of the size of the input data.

    If you want to test N for primality, the amount of data you need to need to give your algorithm is O(log N). (e.g. if your algorithm works in base 10, the size of the input is the number of decimal digits it takes to write N, so the input size is (log N) / log(10))

    So, the size of the input is (log N), and the amount of work necessary is N^(1/2)... which is exponential in the size of the input.

    (Of course, it would be accurate to say that the running time is polynomial in N)
  4. Nov 6, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    The AKS primality test takes O(n6) time* to check if an n-bit number is prime. Trial division takes O(2n/2).

    * The exponent depends on the version used. I think the original was O(n12) time and the best versions so far are conjectured to run in O(n4) time.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Trial division Primality Date
B Divisibility by p^p Jan 25, 2018
E to the -y plus trial and error math? Feb 18, 2014
Probability of an event occurring at least once over n trials Mar 18, 2013
Trial and Error Jan 22, 2011
Sudoku scanning and trial and error Oct 23, 2005