# 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
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:
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

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					     [email protected]
I'm on vacation now, so e-mail will recieve a latency of +/- 24 hours.
PGP Key available from keyservers

```