Category Archives: number theory

Post without words #24

Image | Posted on by | Tagged , , , | 5 Comments

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 , , , | 1 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

Post without words #22

Image | Posted on by | Tagged , , | 8 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