Monthly Archives: August 2018

Efficiency of repeated squaring

Posted on August 24, 2018 by Brent

As you probably realized if you read both, my recent post without words connects directly to my previous post on exponentiation by repeated squaring Each section shows the sequence of operations used by the repeated squaring algorithm to build up … Continue reading →

Posted in computation | Tagged , , , , , , , | 7 Comments

Post without words #22

Posted on August 23, 2018 by Brent
Posted in arithmetic, computation, number theory, posts without words | Tagged , , | 8 Comments

Modular exponentiation by repeated squaring

Posted on August 18, 2018 by Brent

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

Posted on August 13, 2018 by Brent

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 wizard’s rational puzzle (mind your p’s and q’s!)

Posted on August 7, 2018 by Brent

You have been abducted by a sadistic math wizard (don’t you hate it when that happens?). He ushers you into a plain but cozy-looking room, with a hardwood floor, a few exotic-looking rugs, and wood paneling on the walls. He … Continue reading →

Posted in arithmetic, challenges, logic, programming, puzzles | Tagged , , , , , | 15 Comments

The Fermat primality test

Posted on August 3, 2018 by Brent

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