While most practical applications are concerned with the random generation of private keys, anyone who wishes to write unit-testing code on the secp256k1 elliptic curve group may wish to have the ability to randomly generate elliptic curve points.

I can immediately think to two approaches for doing so, one consisting in returning the elliptic point associated with a random secret, the other consisting in randomly generating X, computing X^3 + 7 until we obtain a quadratic residue mod p and compute a square root (which reduces to taking a power (p+1)/4 mod p since p = 3 mod 4). I am suspecting that the latter approach is computationally more efficient as it does not involve the scalar multiplication of the EC group, but only arithmetic operations and exponentiation mod p. Is there a known preferred approach to this question? Assuming my intuition is right, and generating X until X^3 + 7 is a quadratic residue is the way to go, another question naturally arises: what is the preferred approach to test whether a number mod p has a square root? Is it worth implementing the Legendre symbol, or is it better to simply check whether the prospective square root (raising to the power (p+1)/4) fits the bill?

Early optimization is the root of all evil, so maybe I shouldn't be asking this question, especially as the performance of unit testing code probably doesn't matter. But I figure that if some elements of best practice are known regarding bitcoin development, I may as well adopt them and do the right thing.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.