I've just reviewed the Wikipedia entries for RSA and Elliptic Curve, and like 
most 
"Scientific American" level articles it tells you WHAT but not WHY.  For 
example, 
it mentions the totient function, but doesn't explicitly say that the totient 
function counts the number of remaining group members after all the "zero 
divisors" have been cast out.  Similarly, there is a level of detail in the ECC 
stuff 
that is missing, although they did make the major distinction between n>3 
systems (which is the example usually used in "Scientific American" level 
descriptions) and the n=2 systems that are actually in production use.

It's important to realize that given a number k there are exactly 0 or 1 
(distinct) 
finite fields of size k (as opposed to groups, where there may be many 
different 
groups of the same size).  Furthermore, whether there is none at all or exactly 
one can be determined by the prime factorization of k!  If k is of the form P ^ 
j 
where P is a prime number and j is an integer, there is one unique field of 
size 
k.  If k does not fit this pattern, there is NO such field.

So, there is a finite field of size 25 (5 ^ 2) but there is no such field of 
size 6!

And it's not just as simple as using modulo arithmetic.  If you just tried to 
do the 
math mod 25, you are shot down by zero-divisors 5, 10, 15, and 20.  Instead, 
you have to do a 2-vector in which each of the two elements are a number 
modulo 5.  Similarly (and this is key) to do a binary elliptic curve system you 
have a large number (perhaps 192) of vector members each of which is one bit 
(an integer either 0 or 1).  That's what the n=2 means.  Also note that the 
addition modulo 2 used in this system is the XOR operator, so you can use 
word-wide XOR operations to do addition quickly.

The usual pedantry is to consider these vectors to be coefficients in a set of 
polynomials, where for addition you just add corresponding coefficients modulo 
the base field size, and then you have to have some prime polynomial to reduce 
the order of the resulting equation when you multiply.  However, the fact that 
the field is unique (see above) means that even though there may be other ways 
of looking at it, the results are always going to be the same simply because 
the 
base field IS unique. Down to a renaming of elements.

And this is a good insight - choice of a different prime polynomial corresponds 
simply to a renaming of elements (since the base field is unique).

Sorry to pontificobloviate.  Anybody who is interested in the why might be 
interested in at least looking at some of the books I've been able to assemble. 
Anybody else feel free to ignore this.

Reply via email to