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

*To*: [email protected]*Subject*: Q's on Number Theory/Quadriatic Residues*From*: Ben <[email protected]>*Date*: Sun, 13 Aug 1995 19:30:10 -0400*Cc*: [email protected]*Sender*: [email protected]

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

**Follow-Ups**:**Re: Q's on Number Theory/Quadriatic Residues***From:*Derek Atkins <[email protected]>

- Prev by Date:
**EYE_see** - Next by Date:
**Re: Q's on Number Theory/Quadriatic Residues** - Prev by thread:
**Who Else is Reading your Email? (From Cu Digest, #7.67)** - Next by thread:
**Re: Q's on Number Theory/Quadriatic Residues** - Index(es):