Exercises

Some exercises will require theory that will not be lectured. You should read the require theory on your own. If no references are given, you will find the material in Stinson.

Some of the exercises will be in the Department of Mathematical Science's student computer lab 380B (map).

1 - 30/8: Stinson 1.5, 1.10, 1.12, 1.21, 2.2

2 - 6/9: Exercise 2 with supplements supplement-02-a and supplement-02-b, in the computer lab.

3 - 13/9: Stinson 5.1, 5.3, 5.22 and 5.23, in R54.

4 - 20/9: Stinson 6.1, 6.2 and 6.5, in the computer lab. For 6.1, try to figure out how large the group must be for the computer to spend 1 minute what happens first: (a) the computer needs ten minutes to compute the result, or (b) Pari/GP runs out of memory. For 6.5, use Shanks' algorithm as a subroutine, and also compute the logarithm of 448779669284668518559519248801729550530084412761036268891311221899537107169997508638204427416790909697863945298690630246869913882463614155520880819517025716769 for the generator 3 in the field Fp, where p = 515435624341556560362518420756024885206544272775528642664081191900087258070891909746630086045124238045876795573930965747862098723866874422662389356560982867457. (NB! Pari/GP has the builtin function znlog that computes this logarithm. Don't use it.)

5 - 27/9: Stinson 6.3, in the computer lab. (i) Implement Pollard's ρ method, combine it with Pohlig-Hellman and measure the time used to compute discrete logarithms for groups of various sizes (you should find the groups). Compare the time requirements with the theoretical analysis, possibly by using a log-log plot. (ii) A Sophie-Germain prime is a prime q such that 2q+1 is also prime. In cryptography, we call 2q+1 a safe prime. Explain why safe primes seem like a good idea.

Hint: Don't use Pollard's ρ for very small groups, use exhaustive search instead.

Pari/GP note: nextprime is useful to find primes, while znprimroot is useful for finding generators (elements of order p-1).

6 - 4/10: In the computer lab. By hand, do Stinson 6.10, 6.11. Then, on the computer, do: The file index-calculus.gp gives a Pari/GP script to do index calculus in a specific prime field. Adapt the script to do index calculus in galois field with 2^17 elements, and compute the discrete logarithm of x+1 to the base x. You can use the irreducible polynomial x^17+x^3+1.

Hints: (i) You can get the polynomial x^17+x^3+1 in the polynomial ring with f=Mod(1,2)*(x^17+x+1). Then you get the element represented by x+1 in the galois field by Mod( (x+1)*Mod(1,2),f). Results are easier on the eyes if you use lift(lift(…)). (ii) Remember that irreducible polynomials of degree i are factors of x^(2^i)-x. You can find low-degree polynomials by factoring x^(2^i)-x for small i.

7 - 11/10: In the computer lab. Find an elliptic curve defined over the field Fp, p = 1009 with a prime number of points. Adapt Pollard's ρ method for use with elliptic curves, choose two random points on the curve, and compute the discrete logarithm.

Hint: Pari/GP has a number of functions for dealing with elliptic curves. E.g. ellinit, elladd, ellpow and ellap. Use ??ellinit etc. to read the online help.

8 - 18/10: In R54. Stinson, 6.14, 6.15, 6.16 and 6.18.

9 - 25/10: In R54. Stinson, 6.7, 5.10, 5.11, 5.13 and 5.15.

10 - 1/11: In the computer lab. Do Stinson 5.30, then factor the integers 15241578753238836750495351562566681945008382873376009755225118122311263526910001524158887669562727145251813839353713496418224560890107777213839309833866784194634963740588324906171315343828379823619, 742644855298813704818896634696974023721192622558112924768565025164376074343105968357251831005519936272611397151061175987452788044021176530501550810918585785324786829941321808535499664682703324101863228166628303603917454062035256147545990854632486938738322384853375800511235764818230338158101181290162436335659619947958237589958564385897390358539232739097892962917774880776654761 and 10715157602779366933842300254998053345908255974508510081235791334996679460923565808604101521050441837339473771208826364110900996829100644462381378466615825332292672043827549552331720993614307707847414808449352199437817862243645479091160281722649884092473801532899844594756962293781093442366521981537533.

11 - 8/11: In R54. Problem 1, 2 and 3 from the 2008 exam.

12 - 15/11: In R54. Problem 1, 2, 3 and 5 from the 2007 exam.

13 - 22/11: In R54. Problem 1-5 and 7 from the 2005 exam.

Pari/GP is installed on the computer markov.math.ntnu.no, you can start it with the command gp. You can load code from a file x.gp into Pari with the command \r x.gp. Further information about Pari/GP can be found at their home page. (If you prefer, any other computer algebra system could be used instead of Pari/GP.)