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 primeUsing 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:
“I abide by a rule concerning reviews: I will never ask, neither in writing nor in person, that a word be put in about my book.... One feels cleaner this way. When someone asks that his book be reviewed he risks running up against a vulgarity offensive to authorial sensibilities.”
—Anton Pavlovich Chekhov (1860–1904)
“The door is opening. A man you have never seen enters the room.
He tells you that it is time to go, but that you may stay,
If you wish. You reply that it is one and the same to you.
It was only later, after the house had materialized elsewhere,
That you remembered you forgot to ask him what form the change would take.”
—John Ashbery (b. 1927)