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

*To*: [email protected]*Subject*: Re: Diffie Hellman - logs in Galois fields*From*: "Vladimir Z. Nuri" <[email protected]>*Date*: Tue, 17 Sep 96 18:48:49 -0700*cc*: [email protected]*In-reply-to*: Your message of "Mon, 16 Sep 96 14:42:41 -0000." <[email protected]>*Sender*: [email protected]

>A question for the matematicians out there: heh. I'll answer anyway. >My maths tutor has told me a bit about the construction of Galois >fields (If I`m correct the construction is Z mod N, N some integer, >then a transformation F(x) on the residue classes already in the >field) I know also the definition is that there are P**k elements, p >a prime. what is 'k'? there are N elements in the field as I understand the terminology. >1. How can a field be finite, as by definition it has to be closed >under addition, subtraction, multiplication and division???? (sorry >if this one is a bit of a no brainer, maybe the definition is >different but I can`t seem to see how) the short answer is that all the operations are redefined somewhat to analogous operations that map into the range of integers. division is not defined for results that are not integers. actually division is replaced with an operation called "finding the inverse mod n". >2. Why is taking logs in a finite field computationally hard? - Me >and Alec (My maths tutor at college) guessed that it is because >exponentiation and logs are each others inverse functions, and >somehow this becomes a one way function in a finite field. actually, this is a very important question that already gets to the limits of current knowledge. the short answer is that there is *no*proof* that this problem is "hard". in fact such proofs are somewhat rare and exist mostly for contrived problems. in computational theory what one does is prove that your problem is at least as difficult as some other famous problem that many people have tried to find efficient solutions but have failed. this is called "NP Complete". as far as I know there is no proof that "taking logs in a finite field" is actually "hard". in fact there is no proof that factoring (an equivalent form of the problem) is "hard" or even a proof that it is np complete. most of this stuff is in the cryptography faq out there in cyberspace. I am writing in hopes that someone might amend the above by posting the latest academic thinking on the difficulty of factoring.

**References**:

- Prev by Date:
**[NEWS] Crypto-relevant wire clippings** - Next by Date:
**The Near-Necessity of Health Insurance** - Prev by thread:
**Re: Diffie Hellman - logs in Galois fields** - Next by thread:
**Re: Diffie Hellman - logs in Galois fields** - Index(es):