This page generates arbitrarily many random practice problems for you!

Warning:  These are the most basic computational problems.  These are good for making sure you have your basic arithmetic and algorithms down.  But they don’t (and can’t) test conceptual understanding, and test problems may NOT resemble these.

Modular arithmetic.

This box will generate a random addition and multiplication problem.

xxxxxxxxxx

modulus = randint(2,150)

a = randint(0,modulus)

b = randint(0,modulus)

print("Compute ", a, "+", b, " mod ", modulus)

print("Compute ", a, "*", b, " mod ", modulus)

This box will show the answers.

xxxxxxxxxx

print(a, "+", b, " = ", ZZ(Mod(a+b,modulus)), " mod ", modulus)

print(a, "*", b, " = ", ZZ(Mod(a*b,modulus)), " mod ", modulus)

Complex Numbers

xxxxxxxxxx

bd = 10

z = randint(-bd,bd+1)+I*randint(-bd,bd+1)

w = randint(-bd,bd+1)+I*randint(-bd,bd+1)

def complexString(z):

    re = z.real()

    im = z.imag()

    if re == 0 and im == 0:

        return "0"

    comStr = ""

    if re != 0:

        comStr += str(re)

    if im == 0:

        return comStr

    if re == 0:

        if im == 1:

            return "i"

        if im == -1:

            return "-i"

        return str(im) + "i"

    sign = " + "

    if im < 0: sign = " - " comStr += sign if im == 1 or im == -1: comStr += "i" return comStr if im > 0:

        comStr += str(im) + "i"

    else:

        comStr += str(-im) + "i"

    return comStr

zstring = complexString(z)

wstring = complexString(w)

print("What is the complex modulus squared of", zstring, "?")

print("What is", zstring, "plus", wstring, "?")

print("What is", zstring, "times", wstring, "?")

xxxxxxxxxx

print("The complex modulus squared of", zstring, "is", ZZ(round(z.abs()^2)))

print(zstring, "plus", wstring, "=", complexString(z+w))

print(zstring, "times", wstring, "=", complexString(z*w))

Miller-Rabin Primality Testing

These are not designed to be easy by hand, because the first successive squaring part might be annoying; you can use Sage to do the modular arithmetic for you.

xxxxxxxxxx

r = randint(0,2) # decide which type of number: prime, fermat composite, or tricky

n = 1

a=0

if r == 0:

    n = next_prime(randint(2,200))

    a = randint(2,n)

if r == 1:

    n = next_prime(randint(2,100))*next_prime(randint(2,100))

    a = randint(2,n)

if r == 2:

    found = False

    while not found:

        n = next_prime(randint(2,100))*next_prime(randint(2,100))

        a = randint(2,n)

        if Mod(a,n)^(n-1) == Mod(1,n) and Mod(a,n) != Mod(-1,n):

            found = True

print("Perform Miller-Rabin on n=", n, "using the base a=", a)

xxxxxxxxxx

print("n=", n, "and a=", a)

v = QQ.valuation(2)

k = v(n-1)

r = (n-1)/2^k

print(n-1, "= 2^", k, "*",r)

c = Mod(a,n)^r

chain = [c]

for i in range(k):

    c = c^2

    chain.append(c)

print("chain:", chain)

if chain[-1] != 1:

    print("Composite! (Fermat failed)")

else:

    first_index = chain.index(1)

    if first_index > 0:

        previous_value = Mod(chain[first_index-1],n)

        if not ( previous_value == Mod(1,n) or previous_value == Mod(-1,n) ):

            print("Composite! (Surprise square root", previous_value,")")

        else:

            print("Probably prime!")

    else:

        print("Probably prime!")

print("In fact, the factorization is ", factor(n))

RSA Factoring

This box produces RSA moduli that are good for testing your factoring methods on.

xxxxxxxxxx

bits = 10 # change this to make RSA moduli bigger or smaller

halfbits = floor(bits/2)

uplimit = 2^halfbits

lowlimit = 2^(halfbits-1)

a = 1

b = 1

while a == b:

    a = randint(lowlimit,uplimit)

    b = randint(lowlimit,uplimit)

p = nth_prime(a)

q = nth_prime(b)

n = p*q

print("n =", n)

The following box will output the answer.

xxxxxxxxxx

print("n =", factor(n))

Elliptic curve addition.

This box will generate a random elliptic curve point addition problem.

xxxxxxxxxx

p = nth_prime(randint(3,10))

curve = false

while( not curve ):

  coeffs = [0,randint(0,p-1),0,randint(0,p-1),randint(0,p-1)]

  try:

    E = EllipticCurve(GF(p),coeffs)

    curve = true

  except:

    curve = false

pts = E.rational_points()

P = pts[randint(0,len(pts)-1)]

Q = pts[randint(0,len(pts)-1)]

Pstring = "(" + str(P[0]) + "," + str(P[1]) + ")"

Qstring = "(" + str(Q[0]) + "," + str(Q[1]) + ")"

Estring = "y^2 = x^3"

if( E.a2() != 0 ):

    Estring += " + " 

    if( E.a2() != 1 ):

      Estring += str(E.a2()) 

    Estring += "x^2"

if( E.a4() != 0 ):

    Estring += " + "

    if( E.a4() != 1 ):

      Estring += str(E.a4())

    Estring += "x"

if( E.a6() != 0 ):

    Estring += " + " + str(E.a6())

if P == E([0,1,0]):

  Pstring = "infinity"

if Q == E([0,1,0]):

  Qstring = "infinity"

print("Add the elliptic curve points P =", Pstring, "and Q =", Qstring, "on the elliptic curve", Estring, "modulo", p)

This box will show the answer.

xxxxxxxxxx

R = P+Q

Rstring = "(" + str(R[0]) + "," + str(R[1]) + ")"

if R == E([0,1,0]):

  Rstring = "infinity"

print("On the elliptic curve", Estring, "modulo", p, ", ", Pstring, " + ", Qstring, " = ", Rstring, ".")

Elliptic Curve Diffie-Hellman Key Exchange

This box will provide you a key exchange question.

xxxxxxxxxx

p = nth_prime(randint(3,10))

curve = false

while( not curve ):

  coeffs = [0,randint(0,p-1),0,randint(0,p-1),randint(0,p-1)]

  try:

    E = EllipticCurve(GF(p),coeffs)

    curve = true

  except:

    curve = false

pts = E.rational_points()

P = pts[randint(0,len(pts)-1)]

Pstring = "(" + str(P[0]) + "," + str(P[1]) + ")"

if P == E([0,1,0]):

  Pstring = "infinity"

order = P.order()

a = randint(2,order)

b = randint(2,order)

A = a*P

Astring = "(" + str(A[0]) + "," + str(A[1]) + ")"

Estring = "y^2 = x^3"

if( E.a2() != 0 ):

    Estring += " + " 

    if( E.a2() != 1 ):

      Estring += str(E.a2()) 

    Estring += "x^2"

if( E.a4() != 0 ):

    Estring += " + "

    if( E.a4() != 1 ):

      Estring += str(E.a4())

    Estring += "x"

if( E.a6() != 0 ):

    Estring += " + " + str(E.a6())

print("We are doing elliptic curve Diffie-Hellman on the elliptic curve", Estring, "modulo", p, "with the point P =", Pstring)

print("I am Alice.  My public key is A =", Astring)

print("Your secret key is b =", b)

print("What is your public key, and our shared secret?")

This box will show the answer.

xxxxxxxxxx

B = b*P

Bstring = "(" + str(B[0]) + "," + str(B[1]) + ")"

S = a*b*P

Sstring = "(" + str(S[0]) + "," + str(S[1]) + ")"

print("Your public key is B =", Bstring, "and the shared secret is", Sstring)

Elliptic Curve Factoring

This box will generate an example where an elliptic curve computation will help you factor a number. It will typically ask you to multiply a point by 3 or 6. Think about how to do this efficiently! (For 6, don’t just add the point to itself 5 times.)

xxxxxxxxxx

p = nth_prime(randint(3,7))

curve = false

while( not curve ):

  coeffs = [0,randint(0,p-1),0,randint(0,p-1),randint(0,p-1)]

  try:

    E = EllipticCurve(GF(p),coeffs)

    if gcd(E.order(),6) > 1:

      pts = E.rational_points()

      P = pts[randint(0,len(pts)-1)]

      Pord = P.order()

      while gcd(Pord,6) == 1:

        P = pts[randint(0,len(pts)-1)]

        Pord = P.order()

      mult = gcd(Pord,6)

      Q = (Pord/mult)*P

      q = nth_prime(randint(2,15))

      n = p*q

      Eq = EllipticCurve(GF(q),coeffs)

      Qq = Eq([Q[0],Q[1]])

      if (mult*Qq)[2] != 0:

        curve = true

  except:

    curve = false

Qstring = "(" + str(Q[0]) + "," + str(Q[1]) + ")"

Estring = "y^2 = x^3"

if( E.a2() != 0 ):

    Estring += " + " 

    if( E.a2() != 1 ):

      Estring += str(E.a2()) 

    Estring += "x^2"

if( E.a4() != 0 ):

    Estring += " + "

    if( E.a4() != 1 ):

      Estring += str(E.a4())

    Estring += "x"

if( E.a6() != 0 ):

    Estring += " + " + str(E.a6())

if Q == E([0,1,0]):

  Qstring = "infinity"

print("Consider the elliptic curve", Estring, "modulo", n)

print("Factor", n, "by multiplying the point P =", Qstring, "by", mult)

The following box will output the answer.

xxxxxxxxxx

print("n =", factor(n))

Single Qubit States

xxxxxxxxxx

bd = 10

z = randint(-bd,bd+1)+I*randint(-bd,bd+1)

w = randint(-bd,bd+1)+I*randint(-bd,bd+1)

def complexString(z):

    re = z.real()

    im = z.imag()

    if re == 0 and im == 0:

        return "0"

    comStr = ""

    if re != 0:

        comStr += str(re)

    if im == 0:

        return comStr

    if re == 0:

        if im == 1:

            return "i"

        if im == -1:

            return "-i"

        return str(im) + "i"

    sign = " + "

    if im < 0: sign = " - " comStr += sign if im == 1 or im == -1: comStr += "i" return comStr if im > 0:

        comStr += str(im) + "i"

    else:

        comStr += str(-im) + "i"

    return comStr

zstring = complexString(z)

wstring = complexString(w)

print("Consider the state (", zstring, ")|0> + (", wstring, ")|1>.")

print("(1) Normalize this state.")

print("(2) Measure it in the |0>, |1> basis (give outcomes and probabilities).")

print("(2) Write it in the |+>, |-> basis.")

This box will provide the answer.

xxxxxxxxxx

n = ZZ(round(z.abs()^2 + w.abs()^2))

print("The current |a|^2 + |b|^2 of this state is", n, "so we need to divide by sqrt(", n, ").")

znorm = z/sqrt(n)

wnorm = w/sqrt(n)

print("(1) The normalized state is ((", complexString(z), ")/sqrt(", n, "))|0> + ((", complexString(w), ")/sqrt(", n, "))|1>")

print("(2) The probability of outcome |0> is", znorm.abs()^2, ".")

print("and the probability of outcome |1> is", wnorm.abs()^2, ".")

print("(3) Recall that |0> = (1/sqrt(2))|+> + (1/sqrt(2))|-> and |1> = (1/sqrt(2))|+> - (1/sqrt(2))|->.")

a = z + w

b = z - w

nab =  ZZ(round(a.abs()^2 + b.abs()^2))

print("So the given state can be written as ((", complexString(a), ")/sqrt(", nab, "))|+> + ((", complexString(b), ")/sqrt(", nab, "))|->.")

Continued Fractions

xxxxxxxxxx

q = QQ(randint(1,100))/QQ(randint(1,100))

print("Find the continued fraction and approximations for:", q)

xxxxxxxxxx

c = continued_fraction(q)

print("The continued fraction is:", c)

print("The approximations are:", c.convergents())

Lattice Reduction in 2D

xxxxxxxxxx

n = 2 #dimension

N = matrix(ZZ,n,n)

for i in range(n):

  for j in range(n):

    N[i,j] = randint(-10,10)

from sage.matrix.constructor import random_unimodular_matrix

matrix_space = sage.matrix.matrix_space.MatrixSpace(ZZ,2)

M = random_unimodular_matrix(matrix_space)*N

from sage.modules.free_module_integer import IntegerLattice

print("Your matrix is (cols = vectors):")

print(M)

print("Find the shortest vector using basis reduction.")

xxxxxxxxxx

L = IntegerLattice(M.transpose())

v = L.shortest_vector()

print("The shortest vector is", v)

xxxxxxxxxx

​

xxxxxxxxxx

​

xxxxxxxxxx

​

xxxxxxxxxx

​

xxxxxxxxxx

​