tree 29f758b05cfc804eeb842482ab7853e25aab37fc
parent 72791efa1be507f91116e23ed16576c6e78466be
author David Benjamin <davidben@google.com> 1559843047 -0400
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1560464699 +0000

Discuss the doubling case in windowed Booth representation.

Using signed digits for point multiplication halves the size of the table,
which is a valuable optimization. However, it is dependent on the curve whether
the doubling case in point addition is reachable. Assuming my reasoning is
valid, the condition for the standard table strategy is:

  The non-trivial doubling case in single-point scalar multiplication may occur
  if and only if the 2^(w-1) bit of the group order is zero.

It would be nice to transcribe this to Coq someday but, for now, check in a
proof in prose. The condition also does not apply to EC_GFp_nistz256_method's
multi-level tables.

This file is now 91% comments by line count.

Change-Id: I29b394289793db957f99e80734e10ed59a96fcec
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/36364
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>