Re: [Cfrg] Review of ECC topics

[Robert Ransom <[e-mail]>]

On 2/28/14, Watson Ladd <[e-mail]> wrote:
> Some notes, from the concrete to the abstract:
> I do not see what the grade school definition of polynomial has to
> offer above the one recorded below.

The reason that I mention the grade-school definition of “polynomial”
is that (a) everyone is likely to know it, and (b) it's not good
enough for use in abstract algebra, in a very subtle way.  I want to
make sure that the reader sees why that definition is inadequate
before I give the Right definition.

> Furthermore, polynomial addition
> and multiplication are defined so as to make F[x] a commutative ring:
> it is not the case that one can show that the results hold without
> defining the multiplication and addition.

On the contrary, declaring that X satisfies the axioms of a
commutative ring is sufficient to define addition and multiplication
for all polynomials.

More formally:

Let R' be the set of the following:

* x, for each x in F;

* X;

* sum(x, y), for each x, y in R';

* prod(x, y), for each x, y in R'.

Let ~ be the equivalence relation on R' defined as follows, for every
x, y, z in R':

* if x ~ y, then sum(x, z) ~ sum(y, z) and sum(z, x) ~ sum(z, y);

* if x ~ y, then prod(x, z) ~ prod(y, z) and prod(z, x) ~ prod(z, y);

* sum(x, sum(y, z)) ~ sum(sum(x, y), z);

* sum(x, y) ~ sum(y, x);

* sum(0_F, x) ~ x, and sum(x, 0_F) ~ x;

* prod(x, prod(y, z)) ~ prod(prod(x, y), z);

* prod(1_F, x) ~ x, and prod(x, 1_F) ~ x;

* prod(x, sum(y, z)) ~ sum(prod(x, y), prod(x, z));

* prod(sum(x, y), z) ~ sum(prod(x, z), prod(y, z));

* prod(x, y) ~ prod(y, x);

* if x, y are in F, then sum(x, y) ~ x + y and prod(x, y) ~ x*y.

Let R = R'/~; define + and * by [x] + [y] = [sum(x, y)] and [x] * [y]
= [prod(x, y)]; and let 0_R = [0_F] and 1_R = [1_F].  It is obvious
that (if I didn't miss or typo any of the axioms) R is a commutative
ring, that the evaluation homomorphisms (defined in the obvious way)
are well-defined, and that any ring homomorphism from R is defined by
its values at [X] and the embedded elements of F; so R satisfies the
property which defines F[X].

This type of construction is analogous to specifying a group by
generators and relations, or defining the tensor product of modules as
a quotient of a huge free commutative group, or defining an algebraic
extension field F[t] by specifying some polynomial equation which t
satisfies.  It is just as rigorous as the usual constructions of F[X],
and I expect that it will be easier for the non-mathematicians to
grasp.


> Vector space is mentioned but is never defined.

* Everyone who completes an undergraduate course of study in
  engineering or a ‘hard’ science should have had a course in linear
  algebra; at least some other programmers will have seen linear
  algebra (and thus vector spaces over the real numbers) in their
  computing work (e.g. in audio or 3-D graphics programming).

* The concept of a vector space is not especially important here; I
  only mention it to give some idea of the size of an algebraic
  extension field.  If I had needed to use vector spaces over general
  fields for more than that, I would have defined them.


> Despite desiring to avoid algebraic geometry, the world "multiplicity"
> is used without explanation. The parenthetical is an explanation only
> for the initiate or the credulous. Furthermore, to avoid algebraic
> geometry in explaining elliptic curves is to evade the nature of the
> subject. I strongly question the comprehensibility of any such attempt
> in the final reckoning.

* “Multiplicity” is defined for roots of polynomials in one variable
  in high-school algebra.  I don't know whether any reader will
  remember anything about it from then, but if they do, it will help
  them unify the cases of the addition law.

* I don't have an immediate excuse to define “multiplicity” in enough
  detail to be useful as more than a vague concept, but I will have an
  excuse to (and need to) define it if I have to provide proofs that
  the addition and doubling formulas are correct.

* I'm not trying to avoid algebraic geometry at all.  I'm trying to
  include considerably more of algebraic geometry than I have usually
  seen in elementary introductions to elliptic-curve cryptography, so
  that I can explain several critical aspects of Montgomery and
  Edwards curves properly (including twist security and the P_1 * P_1
  form of the Hisil et al. addition formulas).


> An algebraic curve is not the zero set of f(x,y) in some affine plane:
> the field must be algebraically closed for the classical definition,
> and in the modern definition that only is the F_p rational points. In
> particular one runs into the issue of x^p+y^p=0 over F_p, which is not
> the same curve as x+y=0.

Good point.  I'll change the definition of a curve to be the curve's
polynomial equation itself (with appropriate restrictions on the
polynomial), since curves are usually identified with their equations
in practice.

(Also, I see that I screwed up the notation for the affine and
projective spaces; it should be e.g. A^2 with a *super*script 2, not a
subscript 2.)


> Not every morphism is given by a single polynomial, but rather a rule
> assigning to every open set a polynomial in a compatible manner. This
> matters because the addition morphism on a curve in short Weierstrass
> form is not given by a single polynomial, hence the need for complete
> addition laws in the first place.

The need for complete addition laws (a) demonstrates that it is more
important to handle maps which induce partial functions from the
beginning, and (b) demonstrates that it is critical to *not* consider
all curves to be defined over algebraically closed fields.

> (I will temporarily leave aside the
> issue of defining the product to define the addition law as a
> morphism).

Edwards curves live in P_1 * P_1, so I won't be able to avoid the
product of projective spaces.  A product of curves wouldn't be much
harder.


> Your definition of isogeny differs from that of Silverman, the
> standard text in this area. In particular your first condition is
> somewhat mystifying to me: it is not part of the definition of
> Silverman, and so I am concerned the there might actually be a
> difference between them that is material. I have not thought about
> this hard enough to be sure either way. But in one case it is
> unnecessary, and in the other it is wrong.

Thank you for catching that mistake.  Unfortunately, I don't have
Silverman's book, so I tried to piece together the definition of
“isogeny” from what I thought I had learned from other sources, in a
hurry.


> Lastly, intuition does not come from definitions and quoted results.
> It comes from examples. Perhaps "convey the definitions of a few
> critical concepts" would better fit the goals here.

I will add more examples, and the sections on Montgomery and Edwards
curves will provide more, but examples aren't enough.  Good
definitions, and explicit explanations of the underlying concepts (to
the extent that those are possible given the audience), are far more
important, especially when readers will not have the time (or
patience) to slog through dozens of exercises in order to arrive at
insights for themselves.


Thank you for your comments.  I should be able to post an updated
version some time this week.


Robert Ransom