From: "Vladimir Z. Nuri" <vznuri@netcom.com>
Date: Wed, 18 Sep 1996 14:13:00 +0800
To: paul@fatmans.demon.co.uk
Subject: Re: Diffie Hellman - logs in Galois fields
In-Reply-To: <842896368.27767.0@fatmans.demon.co.uk>
Message-ID: <199609180148.SAA28173@netcom3.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



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