I Don\’t Know Enough Math

A lot of my friends are of a more artistic bent, so when I mention something like Google\’s \”{ first 10-digit prime found in consecutive digits of e }.com\” hiring campaign, I usually get a response like \”What\’s e?\” It\’s the kind of thing that makes me think I\’m pretty good at this math stuff. Then something comes along that proves me wrong.

A couple years ago, some smart guys in India came up with a way to determine if a given number is prime. Not too difficult in and of itself, but their method did it in polynomial time (which means it\’s useful for much larger numbers than previous methods).

I wanted to translate this method into Python. Mostly simple, converting an algorithm to a particular language is generally not difficult. But I rammed my head against unfamiliar math.

I know how modular arithmetic works, and so when confronted with something like:

a = r (mod n)

I know to convert it to

sh: /home/pfeilgm/bin/enscript: No such file or directory

in Python. However, the following notation is unknown to me:

a = r (mod x,n)

what is the \”x,n\”? Did I miss some basic math along the way, or is this something I never got to? Please let me know if you have an answer.

BTW, the actual comparison in the algorithm is:

(X + a)n = Xn + a (mod Xr – 1,n)

Comments are closed.