Subject: Reading & graded HW (assignment 4) due Monday, 05Nov2007

Dear Number Theory Enthusiasts

Over the long weekend, please read and Think Deeply About
the rest of chapter 9, sections 9.4, 9.5, 9.6 and 9.7.

/--------------------------------------------------------\
Please type up (or write, but see NOTE below) careful solutions to:
the following four problems.

[NOTE: Wagstaff's symbol "R_m" in #3P.140 is what we call Phi(m); the
units group, multiplicatively, mod m.  See the index for "R_m".  See
pages 127 and 128 for "cyclic group" and "C_m".]

4.1: Please solve #8P.122.

4:2: Please do #3P.140. Give an explicit mapping realizing the isomorphism, with proof.

4:3: Please solve #4P.140. You may take A and B to be
posints. Draw the circle-picture, show the modified patches
that you will use, specify their length, and how many there
are, etc.  Write a formal description of your algorithm,
either in organized-English, or in commented computer-code
(pseudo-code).  Wagstaff's format on pp.130-131 is fine.

4.4: We work modulo M := 191, which is prime.  Its
multiplicative-group, Gamma, has phi(191)=190 elements.  This Gamma is
cyclic, and G := 19 is a generator, i.e Order_Gamma(G)=190.

Use BSGS ("Baby-Step Giant-Step") to compute the unique
exponent  E in [0 .. 190) for which

        [19]^E   =M=  23.

a: As we did in class, draw a large circle-picture and label the entries
of the bottom-right patch by

  G^0 == 1,  G^1 == 19,  G^2 == 170 etc. up to  G^{12} == ??,

putting in the actual values.
  Optional: Produce a sorted version of this list, for binary
searching.

b: Draw in the other patches; how many are there?  By how
much does our last patch overlap our initial patch?

c: What is the value of the multiplier, call it U, which
carries us back to the previous patch?  Now use BSGS to
compute the above E.   Which patch was it in?

d: Use repeated-squaring to check that your value for E is correct.

             ====End of assignment===

Extra credit (small, this is an opportunity to show off): Now imagine
that M is some large composite posint, too big to factor, and G is
some posint coprime to M.  Describe a version of BSGS that computes
the mod-M order of G, and does so in running-time upper-bounded by
Sqrt(M) ...

...well, to be picky, upper-bounded by N*N*Sqrt(M), where N is the
number of bits it takes to describe M.
\________________________________________________________/


/--------------------------------------------------------\
NOTE: I will accept this HW hand-written, but for all subsequent
assignments, there will be a 15% bonus for being typed (or mostly
typed).  I recommend LaTeX (links on on the Teaching Page).

In your solution essays, please start each sentence with a
capitalized word, rather than a math symbol.  Please pull
out significant ideas as separate lemmas.

Please type on every SECOND or every THIRD line (not every line, as I
would like to write between the lines) and please choose a fairly
large font; a 12-point font is good; I have a hard time reading most
10-point fonts.

Homework is due at the beginning of class on Monday, 05Nov2007.
Everyone should turn in his own assignment, but you ARE allowed to
talk with your classmates, to get notes from classmates, to learn
general methods (but not answers) from classmates.
\________________________________________________________/


PS:  In LaTeX you can get double spacing with

    \usepackage{setspace}
    \doublespacing

If you needed to, you can switch back to single spacing with cmd

    \singlespacing


--
Prof. Jonathan LF King   Mathematics dept, Univ. of Florida