Re: New ECC Paper (fast GF(p) point mul)

Tom St Denis <tomstdenis@xxxxxxxxx> wrote:
Turns out you can map from the NIST style to Montgomery style if two
things are true

1. There is at least one root to the equation x^3 - 3x + b in Fp [call
it \alpha]

A rational root x0 of this equation means that (x0,0) is a point on the
curve. (x0,0) is a point of order two. I thought the NIST curves over
prime fields all had prime order (hence no rational points of order 2)?

Now I know how to find roots over Z and R [Newton comes in handy] but
how do you do it over Fp?

Victor Shoup's Number Theory book has this in Chapter 21.

--
Kristian Gjøsteen
.

Relevant Pages

  • Re: New ECC Paper (fast GF(p) point mul)
    ... Kristian Gjøsteen wrote: ... A rational root x0 of this equation means that is a point on the ... curve. ... prime fields all had prime order? ...
    (sci.crypt)
  • Re: Elliptic Curves and Orders
    ... Every point on the curve is a generator ... For prime fields, allowing a small co-factor will dramatically speed ... Sometimes, you can just multiply by the cofactor at suitable places, ...
    (sci.crypt)