From: klbarrus@infocom.net (Karl L. Barrus)
Date: Mon, 14 Aug 95 20:25:50 PDT
To: cypherpunks@toad.com
Subject: Re: Q's on Number Theory/Quadriatic Residues
Message-ID: <199508150325.WAA08157@infocom.net>
MIME-Version: 1.0
Content-Type: text/plain


>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.  

What this means is that 9^2 mod 35 = 11, and 8^2 mod 35 = 29.  See the list
right above the chart that is confusing you.

For example, it lists x^2 = 29 mod 35 has a solution: x = 8,13,22,27

So actually there are 3 other solutions... 13, 22, and 27 are also square
roots of 29 mod 35.

>[ 1/v vs. v-1]
>Are these two expressions interchangeable

Yes.

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

Hm... I forgot.  I have one somewhere and will send it along if I find it.

>Is it possible to predict the possible quadriatic residues, or is an

Yes, you can use the Jacobi symbol to determine if a is a quadratic residue
mod n.  See page 207.

>5)From what does Feige-Fiat-Shamir derive its security?

Difficulty of factoring.
--
Karl L. Barrus <klbarrus@infocom.net>