# 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 **F***p*, 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 2*q*+1 is also prime. In cryptography, we call 2*q*+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 **F***p*, *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.

### About Pari/GP

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.)