[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Q's on Number Theory/Quadriatic Residues

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
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
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 
        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:
        a)On page 293, the residues are listed as, "the possible quadriatic
        Is it possible to predict the possible quadriatic residues, or is an
        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

Ben Samman					     [email protected]
I'm on vacation now, so e-mail will recieve a latency of +/- 24 hours.
		PGP Key available from keyservers