Homework for Mathematics of Information Security
M360: Fall 2004

HW 10: due Friday 10/29

READ: Sections 7.1, 7.4.

BOOK PROBLEMS: none this week.

A. How many roots does f(x)=x^2+x+1 have in Z/2 (i.e. mod 2)? How many roots does f(x)=x^3+x+1 have in Z/2?

B. Find a polynomial of degree 2 that has no roots in Z/5 (i.e. mod 5).

C. If p=3 mod 4 show that f(x)=x^2+1 has no roots in Z/p. Hint: use 3.11 #15.

D. Let f(x)=x^(18)-1 and g(x)=x-1. What are the quotient q(x) and remainder r(x) when you divide f(x) by g(x)?
Repeat this problem for the following 4 choices of g(x): x^2-1, x^3-1, x^6-1, x^9-1.
What do you notice?

E. Find all numbers e between 1 and 18 so that 2^e is a root of f(x)=x^6-1 mod 19.

F. Use the table of powers of 2 mod 19 from class to find all solutions to:
(i) 3x^2=14 mod 19;
(ii) 13x^6=15 mod 19;
(iii) 16x^6=18 mod 19.

G. Find a number n (other than n=8) which has no primitive root (i.e. so that ord_n(a) does not equal phi(n) for any choice of a between 1 and n-1).

H. If g is a primitive root mod 23, for what exponents e is g^e also a primitive root. Hint: Use Ty's conjecture.