akaki (OP)
Newbie
Offline
Activity: 23
Merit: 35
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 19, 2021, 07:09:58 PM Merited by Welsh (2), ABCbits (1) |
|
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) ?
|
|
|
|
_Counselor
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 107
Merit: 61
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 19, 2021, 07:47:28 PM |
|
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.
|
|
|
|
BlackHatCoiner
Legendary
Offline
Activity: 1624
Merit: 7972
Bitcoin is a royal fork
|
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?
|
|
|
|
akaki (OP)
Newbie
Offline
Activity: 23
Merit: 35
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 19, 2021, 08:10:45 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
|
|
|
|
pooya87
Legendary
Offline
Activity: 3556
Merit: 10807
|
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. (-k*G+k*G)= N*G only for (k=1).
That is true for all k values and the result is point at infinity. -k*G + k*G = (N-k)*G + k*G = (N-k+k)*G = N*G = 0*G = infinity
|
|
|
|
NotATether
Legendary
Offline
Activity: 1708
Merit: 7188
In memory of o_e_l_e_o
|
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.
|
|
|
|
akaki (OP)
Newbie
Offline
Activity: 23
Merit: 35
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 20, 2021, 09:00:56 AM |
|
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. (-k*G+k*G)= N*G only for (k=1).
That is true for all k values and the result is point at infinity. -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: -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<N, let's just understand what happens with k=2 that is different from k=1.
|
|
|
|
vjudeu
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 20, 2021, 11:00:47 AM |
|
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 (OP)
Newbie
Offline
Activity: 23
Merit: 35
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 20, 2021, 12:18:19 PM |
|
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.
|
|
|
|
_Counselor
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 107
Merit: 61
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 20, 2021, 01:05:14 PM |
|
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). -2*G + 2*G=(49667982834466148699028630885550314015746939561788444090107179747772288677390, 37758011528734597361759657276645959964664126776856991748971785837209648797521).
Nobody can't help you here, until you explain how exactly you're calculated this numbers
|
|
|
|
akaki (OP)
Newbie
Offline
Activity: 23
Merit: 35
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 20, 2021, 03:33:28 PM |
|
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). -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 : 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
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 107
Merit: 61
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 20, 2021, 05:19:09 PM |
|
Yes, indeed I calculate (-k*G + k*G) as any other EC addition using this function : 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"
|
|
|
|
AliKhan189
Newbie
Offline
Activity: 280
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 20, 2021, 05:45:53 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)〉.
|
|
|
|
akaki (OP)
Newbie
Offline
Activity: 23
Merit: 35
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 20, 2021, 07:46:22 PM Last edit: December 20, 2021, 08:07:47 PM by akaki |
|
Yes, indeed I calculate (-k*G + k*G) as any other EC addition using this function : 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: -k*G+k*G=(0,P) for k€Z, with P = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
The N*G result for k=1 is false, and just coincidence.
|
|
|
|
pooya87
Legendary
Offline
Activity: 3556
Merit: 10807
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 21, 2021, 04:57:55 AM |
|
I'm not sure about that, we can also write: -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): A ≡ B (mod n) kA ≡ kB (mod n)
In other words all the following values are in congruence relation: 0 ≡ N ≡ 2N ≡ 3N ≡ kN (mod N)
|
|
|
|
mausuv
Jr. Member
Offline
Activity: 70
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 26, 2021, 06:58:54 AM |
|
I'm not sure about that, we can also write: -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): A ≡ B (mod n) kA ≡ kB (mod n)
In other words all the following values are in congruence relation: 0 ≡ N ≡ 2N ≡ 3N ≡ kN (mod N)
solve this please example input: # + and - mixed -3942323 56456 -3 -342 -33398 683
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
Offline
Activity: 3556
Merit: 10807
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 26, 2021, 12:12:31 PM |
|
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. -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 2≡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.
|
|
|
|
|