Topic: Secp256k1 returning half of 3G? (Read 146 times)

Don't get overwhelmed by the elliptic curve, first look at how it works from the private key perspective.
In decimal, if we have 3 divided by 2, the result is 1.5.

However, in the finite field that Secp256k1 uses, we don't use fractions. Instead, we find the modular inverse of 2 and multiply it by 3.

This operation is performed modulo n, which is the order of the field,

yielding: 57896044618658097711785492504343953926418782139537452191302581570759080747170

(I was going to write a longer reply, but my iPhone screen glitched and I lost the reply force restarting. Sorry.)

Basically the types it uses are large enough to carry some overflow before it eventually runs out of bits.

BTW: the library is for point operations, so it only does mod P. There's another library, piggypiggy/fp256 on Github, for modular arithmetic with arbitrary modulus.

That "something" is just "3.5". The choice of base point doesn't matter, if you can halve a point G, then you can halve every other point, in exactly the same way.

For example:
If you take "3.5*G", and double it, then you will get "7*G". If you want to halve a point, you can just multiply it by "1/2", which is equal to 0x7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1 in secp256k1.

More than that: not only you can halve a point, but you can also get "one third", "one fifth", and "1/x" for any x-value, in range from 1 to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140.

For example:
And then, if you try to multiply 034C7FF4F2BA8603998339C8E42675CEAC23EF2E9623FDB260B24B1C944A2EA1A9 by three, you will get G, as a result.

To better understand it, you can try some smaller elliptic curve, for example where "p=79, n=67, base=(1,18)". Then, it will be easier to understand, that "1/2=34" in case of this smaller curve, in exactly the same way, as "1/2=7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1" in case of secp256k1. Because "34*2=68=67+1". And that's how you can calculate the inversion: if you multiply "1/x" by "x", then you should get exactly "1", if you compute it modulo "n". It is that simple.

Exactly. And that's the reason, why elliptic curves are safe. In other case, if it would be possible to know, if a given distance between two points is "odd or even", then it would be trivial to break every possible private key.

How does the library "know" when to do regular inverse double 16G-->8G and when to do 7G---->SomethingG...
I am asking because every dot looks like any other dot. You do not know if multiplier*G is odd or even

“To observe that elliptic curve points do not have fractional values, which can cause confusion when attempting to divide or halve a point like 3G. In elliptic curve cryptography (ECC), ‘halving’ a point is done through modular arithmetic, specifically the modular inverse .

For a point such as 3G, you would compute half of it by multiplying it by the modular inverse of 2 (mod N), where N is the curve order. This approach is based on Fermat’s Little Theorem, which allows for efficient computation of the inverse and modular operations .

In secp256k1, for instance, this can be done by calculating modinv(2) * 3G mod N, where N is the curve’s order. This ensures that operations remain within the field defined by the curve, ensuring consistency and avoiding errors that might arise from attempting to directly divide curve points .

By leveraging modular arithmetic, division of points on elliptic curves is avoided and operations stay within the correct field. This avoids potential pitfalls, while still allowing the manipulation of multiples of the base point, G.”

My apologies, the private key operations are mod N, not mod P. Not sure why you had to copy half of my post though.

But if you're using libsecp256k1 then you don't actually have to worry about constructing an N or a P for modulus. The library will reduce the values automatically. All you have to do is use the secp256k1_fe types which you can find in the source code. Those functions are not exported though, so you're not going to find them in a compiled include header.

You need to calculate modinv(2, N) and then multiply that by 3G to get half of it.

When you're calculating half of 3G like this, you are technically calculating (3*(2**(N-2)) mod N)G because of Fermat's little theorem.

Shortcut: 1/2 = modinv(2) = (N+1) / 2 because N is odd = 2**(-1) = 1 * 2**(-1) = 2**(N-1) * 2**(-1) = 2**(N-2) etc

You need to calculate modinv(2G) and then multiply that by 3G to get half of it.

There is no such thing as fractions of a curve point, so "division" is emulated by using modinv and multiplication.

When you're calculating half of 3G like this, you are technically calculating (3*(p-2))G (mod p) because of Fermat's little theorem.

p may be a large number, but you don't have to actually add G that many times, you can convert 3*(p-2) into a bitwise (256-bits) representation, calculate G, 2G, 4G, 8G, 16G, 32G, 64G, 128G, 256G (which is 2^8G btw), 512G, ... (2^255)G and then using the distributive property of addition, add the parts together that make the coefficient equal to 3*(p-2).

So I am exploring this everything and I am learning a lot about bitcoin technical side and structure and also I am learning to programing at Python...

And I made like simple program where you can add dots on elliptic curve like Q+Q or Q+G and also I made G-Q, X*G and

 I made like Q:1/2 so this code will give me for 8G I will get 4G dot...

But when I did that for 3G I expected some error mistake or something because we do not have 1.5G...

So What am I doing wrong here? How I get the result for 3G... or 5G or any odd number * G

Thank you