2016-01-22-homework3.sagews

Math 582: computational number theory

Homework 3 -- due by Wednesday at 9am (that's when I'll grade it)

︠fcaf67de-0ff6-4544-b9f2-d6d494060f6bi︠
%md
**Problem 1:** Make several mathematical objects over a finite fields of your choosing and do at least one thing with them:

- a univariate polynomial

- a matrix

- a vector space

- a multivariate polynomial

- an elliptic curve

- an algebraic curve of genus bigger than 1

Problem 1: Make several mathematical objects over a finite fields of your choosing and do at least one thing with them:

• a univariate polynomial

• a matrix

• a vector space

• a multivariate polynomial

• an elliptic curve

• an algebraic curve of genus bigger than 1

# verify that there are p^2 - ((p^2 - p)/2 + p) = (p^2 - p)/2 irreducible monic quadratic polynomials over F_p
for q in primes(20):
    F = GF(q)
    R.<t> = F[]
    count = 0
    for a in range(q):
        for b in range(q):
            f = t^2 + a*t + b
            if (len(list(f.factor())) == 1 and list(f.factor())[0][1] == 1):
                count = count + 1
    print 'There are', count, 'irreducible monic polynomials of degree 2 over GF(' + str(q) + ')'
    print 'check: (' + str(q) + '^2 - '+ str(q) + ')/2 = ' + str((q^2 - q)/2)

There are 1 irreducible monic polynomials of degree 2 over GF(2) check: (2^2 - 2)/2 = 1 There are 3 irreducible monic polynomials of degree 2 over GF(3) check: (3^2 - 3)/2 = 3 There are 10 irreducible monic polynomials of degree 2 over GF(5) check: (5^2 - 5)/2 = 10 There are 21 irreducible monic polynomials of degree 2 over GF(7) check: (7^2 - 7)/2 = 21 There are 55 irreducible monic polynomials of degree 2 over GF(11) check: (11^2 - 11)/2 = 55 There are 78 irreducible monic polynomials of degree 2 over GF(13) check: (13^2 - 13)/2 = 78 There are 136 irreducible monic polynomials of degree 2 over GF(17) check: (17^2 - 17)/2 = 136 There are 171 irreducible monic polynomials of degree 2 over GF(19) check: (19^2 - 19)/2 = 171

p = 5
F = GF(p); F
R.<t> = F[]; R

Finite Field of size 5 Univariate Polynomial Ring in t over Finite Field of size 5

irreducible = []
for a in range(p):
    for b in range(p):
        f = t^2 + a*t + b
        if len(list(f.factor())) == 1 and list(f.factor())[0][1] == 1:
            irreducible.append(f)
irreducible

[t^2 + 2, t^2 + 3, t^2 + t + 1, t^2 + t + 2, t^2 + 2*t + 3, t^2 + 2*t + 4, t^2 + 3*t + 3, t^2 + 3*t + 4, t^2 + 4*t + 1, t^2 + 4*t + 2]

# Which of these is the Conway polynomial of degree 2 over F_5?
conway_polynomial(5,2).substitute(x = t)

t^2 + 4*t + 2

for n in range(1,6):
    print conway_polynomial(5,n).substitute(x = t)

t + 3 t^2 + 4*t + 2 t^3 + 3*t + 3 t^4 + 4*t^2 + 4*t + 2 t^5 + 4*t + 3

︠4234d124-63ca-46d7-b1cb-277116ed0c75︠
A = matrix(F, 4, 4, lambda i, j: i+j); A

[0 1 2 3] [1 2 3 4] [2 3 4 0] [3 4 0 1]

print 'Eigenvalues of A:', A.eigenvalues()
print '\nminpoly of A:', A.minimal_polynomial()
print 'charpoly of A:', A.characteristic_polynomial()
print '\nrational canonical form of A:'
A.rational_form()
print 'If that looks weird, given charpoly(A), remember that 2 = -3.'
print '\nechelon form of A:'
A.echelon_form()

Eigenvalues of A: [2, 0, 0, 0] minpoly of A: x^3 + 3*x^2 charpoly of A: x^4 + 3*x^3 rational canonical form of A: [0|0 0 0] [-+-----] [0|0 0 0] [0|1 0 0] [0|0 1 2] If that looks weird, given charpoly(A), remember that 2 = -3. echelon form of A: [1 0 4 3] [0 1 2 3] [0 0 0 0] [0 0 0 0]

V = A.kernel(); V

Vector space of degree 4 and dimension 2 over Finite Field of size 5 Basis matrix: [1 0 2 2] [0 1 3 1] 25

V.cardinality()

25

︠b7d0ad95-db24-4d1f-8eb5-af5f7ede042a︠
len(list(V.subspaces(1)))

6

list(V.subspaces(1))

[Vector space of degree 4 and dimension 1 over Finite Field of size 5 Basis matrix: [1 0 2 2], Vector space of degree 4 and dimension 1 over Finite Field of size 5 Basis matrix: [1 1 0 3], Vector space of degree 4 and dimension 1 over Finite Field of size 5 Basis matrix: [1 2 3 4], Vector space of degree 4 and dimension 1 over Finite Field of size 5 Basis matrix: [1 3 1 0], Vector space of degree 4 and dimension 1 over Finite Field of size 5 Basis matrix: [1 4 4 1], Vector space of degree 4 and dimension 1 over Finite Field of size 5 Basis matrix: [0 1 3 1]]

S.<u,v,w> = F[]; S

Multivariate Polynomial Ring in u, v, w over Finite Field of size 5

# a random quadratic form in 3 variables over F_5
coeffs = list(random_vector(F, degree = 10))
g = coeffs[0] + coeffs[1]*u + coeffs[2]*v + coeffs[3]*w + coeffs[4]*u*v + coeffs[5]*u*w + coeffs[6]*v*w + coeffs[7]*u^2 + coeffs[8]*v^2 + coeffs[9]*w^2; g

2*u*w - v*w + 2*u - 2*v - 2*w - 1

g.newton_polytope()
g.newton_polytope().vertices()
g.newton_polytope().plot()

A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 6 vertices (A vertex at (0, 0, 0), A vertex at (0, 0, 1), A vertex at (0, 1, 0), A vertex at (0, 1, 1), A vertex at (1, 0, 0), A vertex at (1, 0, 1))

3D rendering not yet implemented

E = EllipticCurve('11a'); E

Elliptic Curve defined by y^2 + y = x^3 - x^2 - 10*x - 20 over Rational Field

E.conductor()

11

# has good reduction at 5 so...
Ebar = E.change_ring(F); Ebar

Elliptic Curve defined by y^2 + y = x^3 + 4*x^2 over Finite Field of size 5

5 + 1 - E.an(5) == len(Ebar.points())

True

Ebar.genus()

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/schemes/hyperelliptic_curves/hyperelliptic_generic.py", line 229, in genus return self._genus File "sage/structure/parent.pyx", line 855, in sage.structure.parent.Parent.__getattr__ (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/parent.c:8043) attr = getattr_from_other_class(self, self._category.parent_class, name) File "sage/structure/misc.pyx", line 253, in sage.structure.misc.getattr_from_other_class (/projects/sage/sage-6.10/src/build/cythonized/sage/structure/misc.c:1667) raise dummy_attribute_error AttributeError: 'EllipticCurve_finite_field_with_category' object has no attribute '_genus'

Ebar.geometric_genus?

File: /projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/schemes/plane_curves/curve.py
Signature : Ebar.geometric_genus()
Docstring :
Return the geometric genus of the curve.

This is by definition the genus of the normalization of the
projective closure of the curve over the algebraic closure of the
base field; the base field must be a prime field.

Note: This calls Singular's genus command.

EXAMPLE:

Examples of projective curves.

   sage: P2 = ProjectiveSpace(2, GF(5), names=['x','y','z'])
   sage: x, y, z = P2.coordinate_ring().gens()
   sage: C = Curve(y^2*z - x^3 - 17*x*z^2 + y*z^2)
   sage: C.geometric_genus()
         1
   sage: C = Curve(y^2*z - x^3)
   sage: C.geometric_genus()
         0
   sage: C = Curve(x^10 + y^7*z^3 + z^10)
   sage: C.geometric_genus()
         3

Examples of affine curves.

   sage: x, y = PolynomialRing(GF(5), 2, 'xy').gens()
   sage: C = Curve(y^2 - x^3 - 17*x + y)
   sage: C.geometric_genus()
   1
   sage: C = Curve(y^2 - x^3)
   sage: C.geometric_genus()
   0
   sage: C = Curve(x^10 + y^7 + 1)
   sage: C.geometric_genus()
   3

Ebar.geometric_genus()

1

︠43073a3a-73e9-420f-a0d1-d0db294ab785︠

︠01cba624-0243-4c27-ac8a-0e5c4e1e316b︠
Z.<x> = QQ[]
︠d05b8fd2-0fd8-4469-9e7e-9b9b1864608b︠
Hyp = HyperellipticCurve(x^7 - x - 1); Hyp

Hyperelliptic Curve over Rational Field defined by y^2 = x^7 - x - 1

Hyp.genus()

3

Hypbar = Hyp.change_ring(F); Hypbar

Hyperelliptic Curve over Finite Field of size 5 defined by y^2 = x^7 + 4*x + 4

Hypbar.geometric_genus()

3

len(Hypbar.points())

8

︠2db5034f-76e5-49f4-8645-1c0cc05224cd︠

︠94ba8828-bc33-4587-93c2-978df2dcd015︠

︠56f2221a-e6a2-4dca-bd56-bae196a60aa2i︠
%md
**Problem 2:** Benchmark basic arithmetic in $\FF_p$ for $p$ a prime with the following bit sizes: 4, 8, 16, 32, 64, 128, 512.

Problem 2: Benchmark basic arithmetic in $\FF_p$ for $p$ a prime with the following bit sizes: 4, 8, 16, 32, 64, 128, 512.

ell = random_prime(2^512); ell
len(ell.digits())

12391263801719934075147269200624486096905356036881620514867217025022218689728554366094219689708789308158456283076492888957026199314148895275516920490597803 155

for n in [2^e for e in range(2,10)]:
    p = next_prime(2^n);
    print str(n) + '-bit prime: ' + str(p)
    FF = GF(p); FF
    two = FF(2)
    el = FF(ell)
    print 'benchmark for 2 + 2:'
    timeit('two + two')
    print 'benchmark for 2 * 2:'
    timeit('two*two')
    print 'benchmark for ell + ell:'
    timeit('el + el')
    print 'benchmark for ell * ell:'
    timeit('el*el')
    print ''

4-bit prime: 17 Finite Field of size 17 benchmark for 2 + 2: 625 loops, best of 3: 57.6 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 62.2 ns per loop benchmark for ell + ell: 625 loops, best of 3: 56.1 ns per loop benchmark for ell * ell: 625 loops, best of 3: 61 ns per loop 8-bit prime: 257 Finite Field of size 257 benchmark for 2 + 2: 625 loops, best of 3: 57.6 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 62.6 ns per loop benchmark for ell + ell: 625 loops, best of 3: 56.1 ns per loop benchmark for ell * ell: 625 loops, best of 3: 63.7 ns per loop 16-bit prime: 65537 Finite Field of size 65537 benchmark for 2 + 2: 625 loops, best of 3: 114 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 123 ns per loop benchmark for ell + ell: 625 loops, best of 3: 114 ns per loop benchmark for ell * ell: 625 loops, best of 3: 123 ns per loop 32-bit prime: 4294967311 Finite Field of size 4294967311 benchmark for 2 + 2: 625 loops, best of 3: 229 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 294 ns per loop benchmark for ell + ell: 625 loops, best of 3: 229 ns per loop benchmark for ell * ell: 625 loops, best of 3: 304 ns per loop 64-bit prime: 18446744073709551629 Finite Field of size 18446744073709551629 benchmark for 2 + 2: 625 loops, best of 3: 225 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 233 ns per loop benchmark for ell + ell: 625 loops, best of 3: 274 ns per loop benchmark for ell * ell: 625 loops, best of 3: 322 ns per loop 128-bit prime: 340282366920938463463374607431768211507 Finite Field of size 340282366920938463463374607431768211507 benchmark for 2 + 2: 625 loops, best of 3: 230 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 267 ns per loop benchmark for ell + ell: 625 loops, best of 3: 304 ns per loop benchmark for ell * ell: 625 loops, best of 3: 386 ns per loop 256-bit prime: 115792089237316195423570985008687907853269984665640564039457584007913129640233 Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007913129640233 benchmark for 2 + 2: 625 loops, best of 3: 227 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 291 ns per loop benchmark for ell + ell: 625 loops, best of 3: 384 ns per loop benchmark for ell * ell: 625 loops, best of 3: 462 ns per loop 512-bit prime: 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 Finite Field of size 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 benchmark for 2 + 2: 625 loops, best of 3: 230 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 293 ns per loop benchmark for ell + ell: 625 loops, best of 3: 343 ns per loop benchmark for ell * ell: 625 loops, best of 3: 615 ns per loop

︠4a146a53-0f86-4fff-a2a4-f4306b56dd28︠

︠4db7c273-5b06-47ed-99fa-9f95fb13bebe︠

︠dde3f899-3c23-4cb6-8db5-99e53d747db9︠

︠7e5e4644-eeca-4a55-8ac8-1f16de53cbdci︠
%md
**Problem 3:** Benchmark basic arithmetic in $\FF_{p^2}$ for $p$ a prime with the following bit sizes: 4, 8, 16, 32, 64, 128, 512.

Problem 3: Benchmark basic arithmetic in $\FF_{p^2}$ for $p$ a prime with the following bit sizes: 4, 8, 16, 32, 64, 128, 512.

for n in [2^e for e in range(2,10)]:
    p = next_prime(2^n);
    print str(n) + '-bit prime: ' + str(p)
    FF = GF(p^2,'a'); FF
    two = FF(2)
    el = FF(ell)
    print 'benchmark for 2 + 2:'
    timeit('two + two')
    print 'benchmark for 2 * 2:'
    timeit('two*two')
    print 'benchmark for ell + ell:'
    timeit('el + el')
    print 'benchmark for ell * ell:'
    timeit('el*el')
    print ''

4-bit prime: 17 Finite Field in a of size 17^2 benchmark for 2 + 2: 625 loops, best of 3: 59.1 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 57.6 ns per loop benchmark for ell + ell: 625 loops, best of 3: 57.6 ns per loop benchmark for ell * ell: 625 loops, best of 3: 57.6 ns per loop 8-bit prime: 257 Finite Field in a of size 257^2 benchmark for 2 + 2: 625 loops, best of 3: 320 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 386 ns per loop benchmark for ell + ell: 625 loops, best of 3: 318 ns per loop benchmark for ell * ell: 625 loops, best of 3: 386 ns per loop 16-bit prime: 65537 Finite Field in a of size 65537^2 benchmark for 2 + 2: 625 loops, best of 3: 322 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 390 ns per loop benchmark for ell + ell: 625 loops, best of 3: 319 ns per loop benchmark for ell * ell: 625 loops, best of 3: 384 ns per loop 32-bit prime: 4294967311 Finite Field in a of size 4294967311^2 benchmark for 2 + 2: 625 loops, best of 3: 310 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 402 ns per loop benchmark for ell + ell: 625 loops, best of 3: 298 ns per loop benchmark for ell * ell: 625 loops, best of 3: 402 ns per loop 64-bit prime: 18446744073709551629 Finite Field in a of size 18446744073709551629^2 benchmark for 2 + 2: 625 loops, best of 3: 434 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 529 ns per loop benchmark for ell + ell: 625 loops, best of 3: 470 ns per loop benchmark for ell * ell: 625 loops, best of 3: 598 ns per loop 128-bit prime: 340282366920938463463374607431768211507 Finite Field in a of size 340282366920938463463374607431768211507^2 benchmark for 2 + 2: 625 loops, best of 3: 430 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 525 ns per loop benchmark for ell + ell: 625 loops, best of 3: 447 ns per loop benchmark for ell * ell: 625 loops, best of 3: 694 ns per loop 256-bit prime: 115792089237316195423570985008687907853269984665640564039457584007913129640233 Finite Field in a of size 115792089237316195423570985008687907853269984665640564039457584007913129640233^2 benchmark for 2 + 2: 625 loops, best of 3: 443 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 534 ns per loop benchmark for ell + ell: 625 loops, best of 3: 463 ns per loop benchmark for ell * ell: 625 loops, best of 3: 762 ns per loop 512-bit prime: 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 Finite Field in a of size 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171^2 benchmark for 2 + 2: 625 loops, best of 3: 446 ns per loop benchmark for 2 * 2: 625 loops, best of 3: 537 ns per loop benchmark for ell + ell: 625 loops, best of 3: 456 ns per loop benchmark for ell * ell: 625 loops, best of 3: 887 ns per loop

︠7f65ad3d-ff05-4e0b-8224-9969c5870538︠


︠ee1e4474-8413-42d7-9b50-1d5482cb6db2︠

︠706970bc-3997-404d-a300-82d455cf4b81︠

︠6293159f-22be-4675-b607-5ff1160e2668︠

︠6a517ed1-19c5-43f6-8b06-a6359f979c5f︠

︠537fa1a1-325f-4988-a744-34fef7f59ff3︠