## Modular Testing

### November 19, 2013

Today’s exercise is my reminder to myself to do a better job of testing. I was porting some prime-number code to Python, one of several preliminary steps to writing a new essay. I am comfortable enough with Python (mostly), and there is nothing particularly tricky about the code, so I wrote the code, tested it quickly, and went on. Later, a different part of the code was failing, and I couldn’t find the problem. Of course, the problem was in the earlier code that I had quickly tested, and therefore hard to spot, since I was looking in the wrong place. The failing code is shown below.

`def primes(n):`

ps, sieve = [], [True] * (n + 1)

for p in range(2, n + 1):

if sieve[p]:

ps.append(p)

for i in range(p * p, n + 1, p):

sieve[i] = False

return ps

`def isPrime(n):`

if n % 2 == 0:

return n == 2

d = 3

while d * d <= n:

if n % d == 0:

return False

d = d + 2

return True

`def inverse(x, m):`

a, b, u = 0, m, 1

while x > 0:

q = b // x

x, a, b, u = b % x, u, x, a - q * u

if b == 1: return a % m

raise ArithmeticError("must be coprime")

`def jacobi(a, p):`

a = a % p; t = 1

while a != 0:

while a % 2 == 0:

a = a / 2

if p % 8 in [3, 5]:

t = -t

a, p = p, a

if a % 4 == 3 and p % 4 == 3:

t = -t

a = a % p

return t if p == 1 else 0

`def modSqrt(a, p):`

a = a % p

if p % 4 == 3:

x = pow(a, (p+1)/4, p)

return x, p-x

if p % 8 == 5:

x = pow(a, (p+3)/8, p)

c = pow(x, 2, p)

if a != c:

x = (x * pow(2, (p-1)/4, p)) % p

return x, p-x

d = 2

while jacobi(d, p) != -1:

d += 1

t, s = p-1, 0

while t % 2 == 0:

t, s = t / 2, s + 1

at, dt, m = pow(a, t, p), pow(d, t, p), 0

for i in range(0, s):

if pow(at * pow(dt, m), pow(2, s-i-1), p) == p - 1:

m = m + pow(2, i)

x = (pow(dt, m) * pow(a, (t+1)/2, p)) % p

return x, p-x

Your task is to write a proper test suite, discover the bug in the code shown above, and fix it. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.