# Tag Archives: primality

## More on Fermat witnesses and liars

In my previous post I stated, without proof, the following theorem: Theorem: if is composite and there exists at least one Fermat witness for , then at least half of the numbers relatively prime to are Fermat witnesses. Were you … Continue reading

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

## Fermat witnesses and liars (some words on PWW #24)

Let be a positive integer we want to test for primality, and suppose is some other positive integer with . There are then four possibilities: and could share a common factor. In this case we can find the common factor … Continue reading

| Tagged , , , , | 1 Comment

## 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

## 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 | | 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 | | 1 Comment