From: trollins@interactive.visa.com (Tom Rollins)
Date: Fri, 30 Aug 1996 07:13:53 +0800
To: cypherpunks@toad.com
Subject: Elliptic Curve Y**2 = x**3 + a * x**2 + b
Message-ID: <199608291905.PAA16350@rootboy.interactive.visa.com>
MIME-Version: 1.0
Content-Type: text


Hello all,

I have a math question concerning implementation of elliptic
curve systems. In coding some elliptic curve source, I
need to pick a random point on the following elliptic
curve in field F_p where p is a prime number.

       Y**2 = x**3 + a * x**2 + b
       where 4a**3 + 27b**2 is not equal to 0 mod p

In selecting a random point, I pick a random value for
x in the range 0 < x < p, compute the right hand side
of the equation and find myself needing to take the
square root for the two solutions.

Questions are:

  1: How can I take the suqare root mod p ?

  2: How to determine if a solution exists for a
     selected value of x ?

  3: Is the a simpler method than find a square root ?

Thanks for any ideas you may have about this...
-tom