Subject: [Cfrg] Review of ECC topics

From: Robert Ransom <[email-masked]>
Date: Fri, 28 Feb 2014 19:41:35 -0800

See attached for a document reviewing the background in abstract
algebra, number theory, and elliptic curves that I consider necessary
to properly explain the specific design and implementation details of
Montgomery and Edwards curves (including conditions for twist
security, conversion between Montgomery and Edwards forms, conditions
for completeness of the Edwards-form addition law, use of Edwards
forms with a=-1 in fields where -1 is a non-square, and implementation
of simple point formats).

My main goal is to convey the intuition behind a few critical
mathematical concepts; I'm not trying to teach readers to implement
computations involving e.g. algebraic extension fields or Weierstrass
curves.  (Except for the sections on non-squares and square-root
computations, where I can only provide insight without a long
digression for fields in which -1 is a non-square.)

I would greatly appreciate any comments, especially from non-experts.
I am particularly interested in whether the sections on polynomial
rings, algebraic extension fields, and maps between curves (and
elliptic curves) are easy to understand.

Robert Ransom

---

From: Watson Ladd <[email-masked]>
Date: Fri, 28 Feb 2014 20:36:58 -0800

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

Vector space is mentioned but is never defined.

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.

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.

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. (I will temporarily leave aside the
issue of defining the product to define the addition law as a
morphism).

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.

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.

Sincerely,
Watson

On Fri, Feb 28, 2014 at 7:41 PM, Robert Ransom <[email-masked]> wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin