[curves] Another try at point compression

[Robert Ransom]

On 12/17/14, Robert Ransom <rransom.8774 at gmail.com> wrote:

> In my opinion, the main disadvantage of your previous sgn(v)/sqrt(u)
> format was that it absolutely required one exponentiation to pack each
> point.

I was wrong about this.  As the last step of Montgomery-ladder scalar
multiplication by an odd scalar, sqrt(u) can be recovered up to sign
using the Montgomery-form differential addition formulas (just as for
the isogeny-based Edwards x/y point format that you developed in
January) and one batchable inversion, and the sign can be recovered
using one Legendre symbol per point.

And at the end of *any* Edwards-form operation, one can choose P and Q
for some fixed P-Q of sufficiently large order (P-Q should probably be
the standard basepoint) such that P+Q is the desired output, convert P
and Q to projective Montgomery form (on the same curve; no isogeny
needed), and do the same incomplete differential addition, inversion,
and Legendre symbol as for a Montgomery-ladder output.


Robert Ransom