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:

    “If the barricades went up in our streets and the poor became masters, I think the priests would escape, I fear the gentlemen would; but I believe the gutters would simply be running with the blood of philanthropists.”
    —Gilbert Keith Chesterton (1874–1936)

    “His golden locks time hath to silver turned;
    O time too swift, O swiftness never ceasing!
    His youth ‘gainst time and age hath ever spurned,
    But spurned in vain; youth waneth by increasing.
    Beauty, strength, youth are flowers but fading seen;
    Duty, faith, love are roots, and ever green.”
    —George Peele (1559–1596)