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:

    “It is a talent of the weak to persuade themselves that they suffer for something when they suffer from something; that they are showing the way when they are running away; that they see the light when they feel the heat; that they are chosen when they are shunned.”
    —Eric Hoffer (1902–1983)

    “They have gone about the world like wind,
    But little time had they to pray
    For whom the hangman’s rope was spun,
    And what, God help us, could they save?”
    —William Butler Yeats (1865–1939)