Tag Archives: primality

The Fermat primality test and the GCD test

In my previous post we proved that if shares a nontrivial common factor with , then , and this in turn proves that is not prime (by Fermat’s Little Theorem). But wait a minute, this is silly: if shares a … Continue reading

Posted in computation, number theory, primes | Tagged , , , | Leave a comment

Making the Fermat primality test deterministic

Let’s recall Fermat’s Little Theorem: If is prime and is an integer where , then . Recall that we can turn this directly into a test for primality, called the Fermat primality test, as follows: given some number that we … Continue reading

Posted in computation, number theory, primes | Tagged , , , | 1 Comment

Primality testing: recap

Whew, this is developing into one of the longest post series I’ve ever written (with quite a few tangents and detours along the way). I thought it would be worth taking a step back for a minute to recap what … Continue reading

Posted in computation, number theory, primes | Tagged , , , | 2 Comments

Modular exponentiation by repeated squaring

In my last post we saw how to quickly compute powers of the form by repeatedly squaring: ; then ; and so on. This is much more efficient than computing powers by repeated multiplication: for example, we need only three … Continue reading

Posted in computation, number theory | Tagged , , , , , , , | 4 Comments

Modular exponentiation

In my previous post I explained the Fermat primality test: Input: Repeat times: Randomly choose . If , stop and output COMPOSITE. Output PROBABLY PRIME. In future posts I’ll discuss how well this works, things to worry about, and so … Continue reading

Posted in computation, number theory | Tagged , , , | 2 Comments

The Fermat primality test

After several long tangents writing about orthogons and the chromatic number of the plane, I’m finally getting back to writing about primality testing. All along in this series, my ultimate goal has been to present some general primality testing algorithms … Continue reading

Posted in computation, number theory, primes | Tagged , , | 5 Comments

Fast and slow machines

In my previous post, I presented three hypothetical machines which take a positive integer as input and give us something else as output: a factorization machine gives us the complete prime factorization of ; a factor machine gives us one … Continue reading

Posted in computation, number theory, primes | Tagged , , , , , , , , , , | 1 Comment