# ECC Point Multipliers

*From*: tomstdenis@xxxxxxxxx*Date*: 11 Jun 2006 07:27:30 -0700

I'm doing more research into point multipliers. Trying to answer DJBs

challenge of fast random point multiplication. Specially now that I

have decently fast fixed point code :-)

I did a profile of the LTC code and it seems 45% of the time [at least

on my 885] is spent in Montgomery reduction. If I unroll the reduction

code from TFM I get that down to about 41% or so.

Unfortunately the moduli aren't 64-bit friendly (because NIST can't

choose a prime to safe their lives...) so the reduction techniques they

have aren't efficient. A diminished radix approach is faster "on

paper" but in practice not really (unless you inline the whole thing).

Even if I doubled the reduction performance I'm still well above DJBs

performance for Athlon processors.

The real crux of it is that I have to reduce the # of point operations.

Which is why I'm trying to find out as many point multiplier as I can.

So far I've found

1. double-and-add, basic but slow

2. k-ary sliding double/add, what I use now

3. w-NAF and w-FAN, nice on paper, not faster in practice, at least

not on desktops

4. Fixed Point, not useful for this task

5. Montgomery ladders, slow but secure against DPA

In particular, are there ways to compute 2^j * P on prime field curves

with Jacobian co-ordinates faster than doing j doubles (and no, the

trick where you trade 2 squarings for a bunch of additions is not worth

it)? Ideally if I can trade j doubles for j-1 doubles that would

reduce the number of PT doubles I do by a quarter.

Are there efficient ways of computing 2^j * P + Q simultaneously?

I'm toying with the idea of a simultaneous inversion to convert my

k-ary precomp points to affine. But given I only have upto w/4 point

adds the savings will only be 5w/4 mults+reduction [240 for ecc-192,

320 for ECC-256, etc...]. A single inversion cost ~70-100 mults so the

savings will be trivial at best...

Where does DJB get his performance [outside of massively

inlining/unrolling code?]? I thought he was using a k-ary double/add

approach?

Tom

.

**Follow-Ups**:**Re: ECC Point Multipliers***From:*Bodo Moeller

- Prev by Date:
**question regarding Helen Gaines's Cryptanalysis book** - Next by Date:
**THE MATRIX IS PERFECT MORE COMPLEX THEN THE UNIVERSE and if you took a** - Previous by thread:
**question regarding Helen Gaines's Cryptanalysis book** - Next by thread:
**Re: ECC Point Multipliers** - Index(es):