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:

    “People run away from the name subsidy. It is a subsidy. I am not afraid to call it so. It is paid for the purpose of giving a merchant marine to the whole country so that the trade of the whole country will be benefitted thereby, and the men running the ships will of course make a reasonable profit.... Unless we have a merchant marine, our navy if called upon for offensive or defensive work is going to be most defective.”
    —William Howard Taft (1857–1930)

    “I cannot exaggerate the waste of the President’s time and the consumption of his nervous vitality involved in listening to congressmen’s intercession as to local appointments. Why should the President have to have his time taken up in a discussion over ... who shall be the postmistress of Devil’s Lake, in North Dakota? How should he be able to know ... who is best fitted to fill such a place?”
    —William Howard Taft (1857–1930)