Fermat Primality Test - Algorithm and Running Time

Algorithm and Running Time

The algorithm can be written as follows:

Inputs: n: a value to test for primality; k: a parameter that determines the number of times to test for primality Output: composite if n is composite, otherwise probably prime repeat k times: pick a randomly in the range if, then return composite return probably prime

Using fast algorithms for modular exponentiation, the running time of this algorithm is O(k × log2n × log log n × log log log n), where k is the number of times we test a random a, and n is the value we want to test for primality.

Read more about this topic:  Fermat Primality Test

Famous quotes containing the words running and/or time:

    “Do but consider this small dust, here running in the glass,
    By atoms moved.
    Could you believe that this the body was
    Of one that loved?
    And in his mistress’ flame playing like a fly,
    Turned to cinders by her eye?
    Yes, and in death as life unblest,
    To have’t expressed,
    Even ashes of lovers find no rest.”
    —Ben Jonson (1572–1637)

    “I believe that all the survivors are mad. One time or another their madness will explode. You cannot absorb that much madness and not be influenced by it. That is why the children of survivors are so tragic. I see them in school. They don’t know how to handle their parents. They see that their parents are traumatized: they scream and don’t react normally.”
    —Elie Wiesel (b. 1928)