simple pow implementation #554

This adds a secp256k1_scalar_pow which takes two scalars and returns pow(first, second) modulo the group order. It also adds wrappers in eckey and secp256k1 as secp256k1_ec_privkey_tweak_pow.

It should be helpful when using secp256k1 to calculate the jacobi symbol. Right now I believe you need GMP to do so otherwise.

That seems a bit too low level; we try to expose high level API features that are by default safe to use, not expose the internal mathematical operations.

Also, where do you need a Jacobi symbol of a scalar? The Schnorr proposal we wrote up only needs it for field elements (which is already internally implemented as secp256k1_fe_set_xquad).

@sipa Having a way to calculate power-of seems like a natural addition to the priv/pubkey_tweak_add/muls that are there already, IMO. I don't have a strong opinion on the matter though, so I'll remove the secp256k1.h/eckey changes.

What use is there for raising a private key to some power? There isn't even a corresponding public key operation.

Maybe first motivate what application this is useful for before we discuss exposing a primitive.

@sipa I was initially writing this in order to natively calculate the Jacobi symbol. I then realized I'm still missing some components (the biggest issue being that the scalars are modulo n while the jacobi symbol calculation is modulo p).

Perhaps what I'm ultimately aiming for is something like a secp256k1_ec_pubkey_jacobi, but does that implicitly mean "of the X coordinate" as in the Schnorr BIP? If it does, that would probably be useful, no?

@kallewoof Integers modulo p internally are the data type 'secp256k1_fe`, and the Jacobi symbol is already implemented for them (search for "is_quad" somewhere in the source code, I can't look right now).

I don't think there is any use to tweaking private keys by raising them to a power. tweak_add is there for BIP32 and tweak_mul for BIP38.

As far as exposing Jacobi synbols are concerned, I think that's far too low level. It's something internal to the Schnorr scheme, so it'll be implemented as part of an API that can produce signatures and verify them, but not the individual components (the components of ECDSA aren't exposed either).

That's perhaps a difference in philosophy, but I don't want to turn libsecp256k1 into a general math library. That brings in complexity, maintenance overhead for API stability, efficient but portable encodings for all internal data types, and attack surface.

Gotcha! Thanks. I agree about the philosophy to not turn it into a math lib btw.