From: Ben <adept@minerva.cis.yale.edu>
Date: Sun, 13 Aug 95 16:30:32 PDT
To: cypherpunks@toad.com
Subject: Q's on Number Theory/Quadriatic Residues
Message-ID: <199508132330.AA08361@minerva.cis.yale.edu>
MIME-Version: 1.0
Content-Type: text/plain


I've been trying to get myself up to speed on some of the protocols in
_Applied_Cryptography_ and my woeful lack of number theory is showing through
crystal clear.

While a course on number theory is in the works for the fall, right now, I'm
sort
of curious and would appreciate any sort of response I can get to the following 
questions from those of you to whom number theory is not as much of a stranger.

1)In AC on page 293 in the section on the Feige-Fiat-Shamir, there is a 
chart which lists the residues, their inverses and their square roots, all
modulo
35.  The chart, which I have reproduced below, baffles me--at least the part 
for the square roots:

                 -1             -1
        v       v         sqrt(v  )
         1       1               1
         4       9               3
         9       4               2
         11      16              4
         16      11           ***9
         29      29           ***8


***How are these square roots?  9 is certainly not the square root of 11, nor is
8 the square root of 29, even modulo 35.  

2)By the same token, on the previous pages Schneier uses the expression
        (1/v), which I take to mean "the quantity one divided by the value 
                                                   -1
        of v", while the example expresses it as (v  ) which I take to 
        mean "the inverse of v."  Are these two expressions interchangeable
        or is this something that I should have found in the errata?

3)Speaking of errata, where can I find a copy?

4)Now, going back to the number theory, I've got a few more questions re:
quadriatic
residues.
        a)On page 293, the residues are listed as, "the possible quadriatic
residues"
        Is it possible to predict the possible quadriatic residues, or is an
exhaustive
        search of the values from on the interval [1,n] necessary to find the 
        quadriatic residues of modulo n?


5)From what does Feige-Fiat-Shamir derive its security?  Obviously not
discrete logs,
but I'm not sure I understand the protocol sufficiently to be able to see
where it 
derives its security.

To those of you who aren't interested, thanks for reading so far, and with
this we
return you to your regularly scheduled conspiracy rants, personal attacks,
and other 
random nonsense.  To those of you who can respond, any assistance is
appreciated.

Ben.
***********************************************************************
Ben Samman					     Samman@cs.yale.edu
I'm on vacation now, so e-mail will recieve a latency of +/- 24 hours.
		PGP Key available from keyservers