# Posts

16 June 2019 / /

## A suspiciously fast program

Computing large integer powers modulo some number is a somewhat common operation. For example, it’s used in RSA encryption. Usually, this is done using exponentiation by squaring, but this go program correctly prints the results of $n^{2^{64}}\ (\mathrm{mod}\ 115763)$ for $n$ from 1 to 20, seemingly naively:

package main

import "fmt"

func main() {
for n := 1; n <= 20; n++ {
result := 1
for i := 0; i < 2^64; i++ {
result = (result * n) % 115763
}
fmt.Printf("pow(%d, pow(2, 64)) mod 115763 = %d\n", n, result)
}
}


It runs, unoptimized, in a few milliseconds on my desktop. You can run it yourself online using the go playground. Feel free to edit the code a little before running it to convince yourself it’s not just fast because the playground is caching the results or something.

How can it be that fast? Is go’s optimizing compiler that clever? It’s not, and there’s a trick in the code. Can you see it?

14 June 2019 / /

## Generating random Latin squares

21 May 2015 / / /

## Near-optimal closed-hand Chinese Poker.

This blog post looks at closed-hand Chinese Poker, and describes a near-optimal strategy for it which is readily implementable on a computer.