Re: Fundimentals of Elliptic Curves for a newbe
From: Arturo Magidin (magidin_at_math.berkeley.edu)
Date: 05/23/03
- Next message: Paul Rubin: "Re: Power consumption attacks on RSA"
- Previous message: Tom St Denis: "Re: Fundimentals of Elliptic Curves for a newbe"
- In reply to: John M. Dlugosz: "Fundimentals of Elliptic Curves for a newbe"
- Next in thread: Phil Carmody: "Re: Fundimentals of Elliptic Curves for a newbe"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Fri, 23 May 2003 19:48:34 +0000 (UTC)
In article <968f09a.0305231135.522b7960@posting.google.com>,
John M. Dlugosz <john@dlugosz.com> wrote:
>This is starting to make sence. Can y'all tell me if I'm getting this
>right, and help with some of the details around the edges?
>
>? fields over a prime and fields over 2^n are fundimentally different
>beasts, not simply a large prime vs. a large power of two with the
>same math. The former uses mod int arithmetic, the latter uses
>polynomials.
Actually, the difference is between fields of prime order, and fields
of order a power of a prime. But what you are talking about is the
representation of those fields, not really what the fields "are".
In general, a field of order p^n, p a prime, n>1, is easier to
describe using polynomials, but this is not always the case. For
example, the field of 9 elements can also described as consisting of
all elements of the form a+bi, with a,b integers taken modulo 3, and i
the complex number whose square is -1 (that is, i^2=-1=2), so we would
again be using modular arithmetic rather than polynomials.
>? the above being true, it's simply confusing to write F<sub>p</sub>
>and F<sub>2<super>n</super></sub> (to borrow notation from HTML) to
>refer to them.
You are confusing how you describe something with what that something
is. All these fields are really part of a single family of objects
with the same sort of properties, hence the same nomenclature for all
of them.
>? Sources other than this book use GF. I suppose that means "Galois
>Field" and refers specifically to the polynomial one. So GF(2^n)
>means the polynomial field with n powers of x and mod 2 coeficients.
No. It does not "mean" that. First, there is no "polynomial field";
you need to specify a primitive polynomial so you can talk about
multiplication (otherwise, multiplication of polynomials doesn't work
out: the product of a polynomial of degree 1 by a polynomial of degree
1 would be a polynomial of degree 2, too large a degree). So, for
example, GF(4) is not just {0, 1, x, 1+x}, because if we take x(1+x)
what do we get? Instead, you need to specify that you are taking these
polynomials, and doing addition and multiplication modulo a polynomial
like 1+x+x^2, so that x(1+x) = x+x^2 = 1 (mod (1+x+x^2)).
"GF" means Galois Fields, and is simply another name for finite
fields, since they were first described by Galois.
>? It doesn't say anything about the irreducible prime polynomial
>needed for multiplication in the field, though. Just pick one, or
>what?
Pick any primitive polynomial. The theory of Galois Fields guarantees
that whatever one you pick, and whatever one I pick, we will end up
with isomorphic fields, in which your 0 and your 1 correspond to my 0
and my 1.
[.snip.]
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu
- Next message: Paul Rubin: "Re: Power consumption attacks on RSA"
- Previous message: Tom St Denis: "Re: Fundimentals of Elliptic Curves for a newbe"
- In reply to: John M. Dlugosz: "Fundimentals of Elliptic Curves for a newbe"
- Next in thread: Phil Carmody: "Re: Fundimentals of Elliptic Curves for a newbe"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
