zero point of secp256k1 | Bitcointalksearch.org

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: mausuv on December 26, 2021, 01:58:54 AM

solve this please

Code:

example input: # + and - mixed
-3942323
56456
-3
-342
-33398
683

Code:

output : #always positive value
3942323
56456
3
342
33398
683

i know abs() method returns the absolute value of a number and √(x^2) = all value positive

i need math steps
example:
https://www.wolframalpha.com/input/?i=3942323%2F-1+*++-1
https://www.wolframalpha.com/input/?i=-3942323%2F-1+*++-1

√(x^2) = only rootsqure alternative method maths explain please #mybad english

I'm not sure what you are asking me to solve but in modular arithmetic we aren't arbitrarily changing the sign of a negative number to positive. Instead the congruent number is computed.
For example if the modulus is 7 then -1 becomes 6 or -9 becomes 5.
Essentially we compute (a mod m) then if the result was negative we add modulus to the result.

Code:

-9%7=-2 -> -2+7=5 -> -9 ≡ -2 ≡ 5 (mod 7)

As for square root, it is also different in modular arithmetic. You have to compute r so that r²≡a (mod p).
For secp256k1 curve we have a simple solution to compute ModPow(a, (p+1)/4, p) but in general cases where p%4 != 3 we have to use an algorithm like Tonelli–Shanks.

mausuv

jr. member

Activity: 70

Merit: 1

Quote from: ?? on ??

Quote from: pooya87 on December 20, 2021, 11:57:55 PM

Quote from: akaki on December 20, 2021, 04:00:56 AM

I'm not sure about that, we can also write:

Code:

-1*G + 1*G = N*G
-2*G + 2*G = (-1*G - 1*G) + (1*G +1*G) = 2N*G
...
-k*G + k*G = N*K*G

FWIW in modular arithmetic we have compatibility with scaling (for any integer k):

Code:

A ≡ B (mod n)
kA ≡ kB (mod n)

In other words all the following values are in congruence relation:

Code:

0 ≡ N ≡ 2N ≡ 3N ≡ kN (mod N)

solve this please

Code:

example input: # + and - mixed
-3942323
56456
-3
-342
-33398
683

Code:

output : #always positive value
3942323
56456
3
342
33398
683

i know abs() method returns the absolute value of a number and √(x^2) = all value positive

i need math steps
example:
https://www.wolframalpha.com/input/?i=3942323%2F-1+*++-1
https://www.wolframalpha.com/input/?i=-3942323%2F-1+*++-1

√(x^2) = only rootsqure alternative method maths explain please #mybad english

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: akaki on December 20, 2021, 04:00:56 AM

I'm not sure about that, we can also write:

Code:

-1*G + 1*G = N*G
-2*G + 2*G = (-1*G - 1*G) + (1*G +1*G) = 2N*G
...
-k*G + k*G = N*K*G

FWIW in modular arithmetic we have compatibility with scaling (for any integer k):

Code:

A ≡ B (mod n)
kA ≡ kB (mod n)

In other words all the following values are in congruence relation:

Code:

0 ≡ N ≡ 2N ≡ 3N ≡ kN (mod N)

akaki

newbie

Activity: 25

Merit: 35

Quote from: _Counselor on December 20, 2021, 12:19:09 PM

Quote from: akaki on December 20, 2021, 10:33:28 AM

Yes, indeed I calculate (-k*G + k*G) as any other EC addition using this function :

Code:

LamAdd = ((b[1] - a[1]) * modinv(b[0] - a[0], P)) % P

As I said before, there is no exists inverse of zero (a[0] = b[0], b[0]-a[0] = 0)

If you modinv() function returning something with a zero argument, this is mean that is a wrong (or simplified - without error checking) implementation of modular multiplicative inverse. And that is why you're getting unexpected strange numbers in result.

Basically, zero-point, or identity point cannot be calculated, it is defined as [0;1;0] in projective coordinates or [P,0] in affine. Due to all of this, addition algorithms should contain something like "if (p1.y != p2.y and p1.x == p2.x) return zero"

Thanks, I updated my modinv function.

conclusion of discussion:

Code:

-k*G+k*G=(0,P) for k€Z, with P = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

The N*G result for k=1 is false, and just coincidence.

AliKhan189

newbie

Activity: 280

Merit: 0

Quote from: akaki on December 19, 2021, 02:09:58 PM

Hello,

I need a math clarification please.

Since the points on the Elliptic Curve (secp256k1) form a group, we can apply the laws of addition, substruction and multiplication.

This require a zero.

I checked that -1*G+1*G=N*G (with N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141).

Therefore, could we consider N*G as the zero ?

If yes, then why -2*G+2*G = M such as there seems to be no link between M and N.

Generaly speaking, is there any link between (-1*G+1*G) and (-k*G+k*G) ?

Prove that if ϕ : G → H is a group homomorphism and G is cyclic, then the subgroup ϕ(G) is cyclic. Proof Suppose G is cyclic, so G = 〈a〉 = {ak : k ∈ Z} for some a ∈ G. ... Then, as a generates G, we have c = ak for some integer k. Thus b = ϕ(c) = ϕ(ak) = ϕ(a)k ∈ 〈ϕ(a)〉.

_Counselor

member

Activity: 111

Merit: 61

Quote from: akaki on December 20, 2021, 10:33:28 AM

Yes, indeed I calculate (-k*G + k*G) as any other EC addition using this function :

Code:

LamAdd = ((b[1] - a[1]) * modinv(b[0] - a[0], P)) % P

As I said before, there is no exists inverse of zero (a[0] = b[0], b[0]-a[0] = 0)

If you modinv() function returning something with a zero argument, this is mean that is a wrong (or simplified - without error checking) implementation of modular multiplicative inverse. And that is why you're getting unexpected strange numbers in result.

Basically, zero-point, or identity point cannot be calculated, it is defined as [0;1;0] in projective coordinates or [P,0] in affine. Due to all of this, addition algorithms should contain something like "if (p1.y != p2.y and p1.x == p2.x) return zero"

akaki

newbie

Activity: 25

Merit: 35

Quote from: _Counselor on December 20, 2021, 08:05:14 AM

Quote from: akaki on December 20, 2021, 07:18:19 AM

Maybe the zero infinity point is just an abstract notion and therefore we are not allowed to calculate (-k*G + k*G) as a normal addition.

You can't calculate -P+P in a "normal" way, because this points have same X, so it will lead to division by zero (or, if we talking about EC math - multiplicative modular inverse of zero which doesn't exist).

Quote from: akaki

-2*G + 2*G=(49667982834466148699028630885550314015746939561788444090107179747772288677390, 37758011528734597361759657276645959964664126776856991748971785837209648797521).

Nobody can't help you here, until you explain how exactly you're calculated this numbers

Yes, indeed I calculate (-k*G + k*G) as any other EC addition using this function :

Code:

def ECadd(a, b):
LamAdd = ((b[1] - a[1]) * modinv(b[0] - a[0], P)) % P
x = (LamAdd * LamAdd - a[0] - b[0]) % P
y = (LamAdd * (a[0] - x) - a[1]) % P
return x, y

It seems to work for K=1 as I get N*G (verified by EC multiplication).

What would be the modification to have the correct result for any K ? If it's not supposed to be always the same, does it have any link with k=1 ?

_Counselor

member

Activity: 111

Merit: 61

Quote from: akaki on December 20, 2021, 07:18:19 AM

Maybe the zero infinity point is just an abstract notion and therefore we are not allowed to calculate (-k*G + k*G) as a normal addition.

You can't calculate -P+P in a "normal" way, because this points have same X, so it will lead to division by zero (or, if we talking about EC math - multiplicative modular inverse of zero which doesn't exist).

Quote from: akaki

-2*G + 2*G=(49667982834466148699028630885550314015746939561788444090107179747772288677390, 37758011528734597361759657276645959964664126776856991748971785837209648797521).

Nobody can't help you here, until you explain how exactly you're calculated this numbers

akaki

newbie

Activity: 25

Merit: 35

Quote from: vjudeu on December 20, 2021, 06:00:47 AM

Quote

Therefore, there is probably a different "infinity" point for each pair (-k*G, k*G), which is in accordance with the fact that addition of x-axis symetrical points forms parallel lines.

No, the point is the same. For every public key Q you have nQ=O, where O is the infinity point (0,0). If you have different results, then (as _Counselor mentioned) "you should check your calculations". For two points, where you have d and (-d), your y-value of the public key after addition should be equal

Aditions of the pairs (-k*G, k*G) give each time a different (x,y) result, so please don't add entropy to the discussion.

Maybe the zero infinity point is just an abstract notion and therefore we are not allowed to calculate (-k*G + k*G) as a normal addition.

Yet, having -1*G + 1*G = N*G could help finding a relationship with -k*G + k*G that gives a point with arbitrary-looking cooridnates. An example was given with k=2.
Any help is welcome after verification.

vjudeu

copper member

Activity: 909

Merit: 2301

Quote

Therefore, there is probably a different "infinity" point for each pair (-k*G, k*G), which is in accordance with the fact that addition of x-axis symetrical points forms parallel lines.

No, the point is the same. For every public key Q you have nQ=O, where O is the infinity point (0,0). If you have different results, then (as _Counselor mentioned) "you should check your calculations". For two points, where you have d and (-d), your y-value of the public key after addition should be equal to zero.

akaki

newbie

Activity: 25

Merit: 35

Quote from: pooya87 on December 19, 2021, 11:23:30 PM

Quote from: akaki on December 19, 2021, 02:09:58 PM

Therefore, could we consider N*G as the zero ?

It is not zero, it is called infinity point. Essentially to compute k*G if k%N = 0 then we get point at infinity.

Quote from: akaki on December 19, 2021, 03:10:45 PM

(-k*G+k*G)= N*G only for (k=1).

That is true for all k values and the result is point at infinity.

Code:

-k*G + k*G = (N-k)*G + k*G = (N-k+k)*G = N*G = 0*G = infinity

I'm not sure about that, we can also write:

Code:

-1*G + 1*G = N*G
-2*G + 2*G = (-1*G - 1*G) + (1*G +1*G) = 2N*G
...
-k*G + k*G = N*K*G

Therefore, there is probably a different "infinity" point for each pair (-k*G, k*G), which is in accordance with the fact that addition of x-axis symetrical points forms parallel lines.

However, in reality with k=2, we get a point not equal to 2N*G and with no apparent link to N*G :
-2*G + 2*G=(49667982834466148699028630885550314015746939561788444090107179747772288677390, 37758011528734597361759657276645959964664126776856991748971785837209648797521).

So for me the question still needs clarifications.

Before generalizing the formula to any K

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: BlackHatCoiner on December 19, 2021, 02:54:05 PM

I'm not 100% sure for this, but you can't subtract this way in ECC.

Think of this. 1*G - 1*G would be equal with 1*G + (-1)*G, right? But, -1 is outside the range. In finite fields, -1 is equal with N-1 which is 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364139.

So, what you really do is 1*G + (N-1)*G which is N*G. Apparently, k*G + (-k)*G is always N*G, but I need this to be confirmed. Anyway, check: How to subtract two points on an elliptic curve?

Subtracting a point by itself always leads to zero because one of the points is at the top of the Y axis, the other is on the bottom of the Y axis but has the same X coordinate so they just have a flipped Y coordinate.

Since subtraction is just negative addition, and point addition just finds the third point on the curve that forms a line with the other two points, when you're subtracting a point from itself that third, intermediate point does not exist so it passes through the infinity point that's in three-dimensional space, which is how you arrive at the 0G result. It would not be equal to -1G.

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: akaki on December 19, 2021, 02:09:58 PM

Therefore, could we consider N*G as the zero ?

It is not zero, it is called infinity point. Essentially to compute k*G if k%N = 0 then we get point at infinity.

Quote from: akaki on December 19, 2021, 03:10:45 PM

(-k*G+k*G)= N*G only for (k=1).

That is true for all k values and the result is point at infinity.

Code:

-k*G + k*G = (N-k)*G + k*G = (N-k+k)*G = N*G = 0*G = infinity

akaki

newbie

Activity: 25

Merit: 35

Quote from: BlackHatCoiner on December 19, 2021, 02:54:05 PM

I'm not 100% sure for this, but you can't subtract this way in ECC.

Think of this. 1*G - 1*G would be equal with 1*G + (-1)*G, right? But, -1 is outside the range. In finite fields, -1 is equal with N-1 which is 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364139.

So, what you really do is 1*G + (N-1)*G which is N*G. Apparently, k*G + (-k)*G is always N*G, but I need this to be confirmed. Anyway, check: How to subtract two points on an elliptic curve?

yes, by -1*G, I mean also (N-1)*G.

I'm sure of my calculations. At least the apparent result is that (-k*G+k*G)= N*G only for (k=1). This could be possible since the addition of pairs (-k*G,k*G) on the curve form parallel lines.

Then, the question is about the link between the sums.

For K=1:
(20860373710434931919338205163613943089612844706565330860427609212248504954008, 28589774168867891354814021154080592739878697919018203946384876578134205873990) = N*G

For K=2:
(49667982834466148699028630885550314015746939561788444090107179747772288677390, 37758011528734597361759657276645959964664126776856991748971785837209648797521) = x*G

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

I'm not 100% sure for this, but you can't subtract this way in ECC.

Think of this. 1*G - 1*G would be equal with 1*G + (-1)*G, right? But, -1 is outside the range. In finite fields, -1 is equal with N-1 which is 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364139.

So, what you really do is 1*G + (N-1)*G which is N*G. Apparently, k*G + (-k)*G is always N*G, but I need this to be confirmed. Anyway, check: How to subtract two points on an elliptic curve?

_Counselor

member

Activity: 111

Merit: 61

Zero point in secp256k1 is point with zero Y (X = P = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
All basic calculations is applies in EC math, so: -k1*G+k1*G = -k2*G+k2*G = zero
I don't know why are you get different results with 1*G and 2*G, you should check your calculations.

akaki

newbie

Activity: 25

Merit: 35

Hello,

I need a math clarification please.

Since the points on the Elliptic Curve (secp256k1) form a group, we can apply the laws of addition, substruction and multiplication.

This require a zero.

I checked that -1*G+1*G=N*G (with N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141).

Therefore, could we consider N*G as the zero ?

If yes, then why -2*G+2*G = M such as there seems to be no link between M and N.

Generaly speaking, is there any link between (-1*G+1*G) and (-k*G+k*G) ?

Topic: zero point of secp256k1 (Read 364 times)