Potatotom: Song’s book is on order. Hopefully that will be a thank you moment.
A follow up question. The elliptic curve under discussion is defined as:
Y2 = x3 + ax + b where a = 0 and b = 7 giving us
Y2 = x3 + 7
To plot the curve we use exponentiation, which is repetitive multiplication. And multiplication is repetitive addition.
Begin with point G on this curve, called the Generator Point. If we have a private key of 0X0002, decimal value two, then the public address is the same as G added to itself, or G multiplied by 2.
I recognize that if we look at the curve, maybe graphed to show the two points, we cannot simply multiply point G by 2 to get the public address. Or simply add G to G itself. Those operations are not valid and don’t make sense.
We must apply the arithmetic in accordance with the rules of the curve.
But, we do have rules by which we can double G and/or add G to itself. One set of rules has an equation that is used to calculate temporary variable used to determine the x and y values of the new point. That one is:
s = ( 3 * (p1x) ** 2 + a ) / ( 2 * ( p1y ) )
This equation is about 2/3rds down the web page referenced above, under the header Double. The equation uses color which will not work well here so I use p1x and p1y to refer to the x and y values of the first point.
The first question is trivial: What does the a represent? Is this the “a” from the equation where a = 0 and b = 7. It may be a constant in the code but this is not apparent from the snippet provided. In that case, it is interesting that “b” does not make an appearance in the doubling equations.
The second is a bit more involved. Within the equation, we are using addition, multiplication, and exponentiation. Not to the point itself, but to the constituent parts of the point, in accordance with the rules of the elliptic curve.
To support this, mostly to verify or show wrong my claims, please visit to that web page, open the code section under “Double” and see that these regular arithmetic operations are utilized.
Why is division to the constituent parts of the point prohibited?
Edit: shortly after posting, while doing something else, this thought occurred to me: Division is prohibited because it can, and more often than not, result in non-integer results.
Hmmm, but maybe that can be mitigated with some rules about those non-integral results.
Topic: modular inverse in bitcoin arithmetic (Read 69 times)
Short answer: that was quite unexpected.
Long answer: Need more time to make a reasonable reply, much less comprehensive.
Stated in other words, absolutely essential.
Thank you very much for your time and patience.
Long answer: Need more time to make a reasonable reply, much less comprehensive.
Stated in other words, absolutely essential.
Thank you very much for your time and patience.
I found Jimmy Song's "programming bitcoin" very interesting !
The arithmetic you have in mind is a special case of general arithmetic, so what you're missing are the fundamental concepts.
Groups, rings, fields, which can be either finite or infinite. Rational numbers are just an example of an infinite field.
Division does not exist, since it is simply defined as the inverse value of a multiplication. So if a group is defined as a structure that only defines one operation (addition) between two elements, then there is no such thing as a multiplication (it can't be called a group anymore). The same way that if you have a multiplicative group, there is no addition on it, just multiplication.
And if you have a field (or even a group), every element's inverse is the one that, when added or multiplied by it, results as the neutral element:
Additive Group / Field: a + inv(a) = 0 (0 is neutral element of addition) - in a field, this is the "inverse of addition operation" / opposite / negated a
Multiplicative Group / Field: a * inv(a) = 1 mod N (1 is neutral element of multiplication) - "inverse of multiplicative operation"
which if you examine carefully, is valid for rational numbers, since a/b = a * 1/b, so a * inv(b) = 1
Next, you want to learn about the Lagrange theorem, Fermat's theorems, Euclid's extended GCD algorithm, and modern binary extended GCD, which are the most efficient ways currently known to compute a finite field element's inverse, since this it is the most time-consuming operation and no one figured out in the last 2000 years if it's a P or nP class problem.
Groups, rings, fields, which can be either finite or infinite. Rational numbers are just an example of an infinite field.
Division does not exist, since it is simply defined as the inverse value of a multiplication. So if a group is defined as a structure that only defines one operation (addition) between two elements, then there is no such thing as a multiplication (it can't be called a group anymore). The same way that if you have a multiplicative group, there is no addition on it, just multiplication.
And if you have a field (or even a group), every element's inverse is the one that, when added or multiplied by it, results as the neutral element:
Additive Group / Field: a + inv(a) = 0 (0 is neutral element of addition) - in a field, this is the "inverse of addition operation" / opposite / negated a
Multiplicative Group / Field: a * inv(a) = 1 mod N (1 is neutral element of multiplication) - "inverse of multiplicative operation"
which if you examine carefully, is valid for rational numbers, since a/b = a * 1/b, so a * inv(b) = 1
Next, you want to learn about the Lagrange theorem, Fermat's theorems, Euclid's extended GCD algorithm, and modern binary extended GCD, which are the most efficient ways currently known to compute a finite field element's inverse, since this it is the most time-consuming operation and no one figured out in the last 2000 years if it's a P or nP class problem.
Points are made of two coordinates x and y that are integers and the arithmetic is performed on those integers.
It is all modular arithmetic as well and inverse or modular multiplicative inverse of "a" is another integer "b" if when multiplied by "a" the result is congruent to 1 modulo "m". Meaning:
It is all modular arithmetic as well and inverse or modular multiplicative inverse of "a" is another integer "b" if when multiplied by "a" the result is congruent to 1 modulo "m". Meaning:
Code:
ab ≡ 1 (mod m)
Code:
a = 4
m = 7
b = 2
ab ≡ 4*2 ≡ 8 ≡ 1 (mod 7)
m = 7
b = 2
ab ≡ 4*2 ≡ 8 ≡ 1 (mod 7)
Post on bitcointalk in technical discussion
I am trying to understand the bitcoin arithmetic, as opposed to the mathematics. A couple of websites mention that dividing with the elliptic curve points is impractical so they multiple by the inverse. Just in case it matters my primary reference is this site:
https://learnmeabitcoin.com/technical/cryptography/elliptic-curve/
Trying to stay with the basics, multiply a by the inverse of b is the same as dividing by b. But arithmetically the inverse of a is found by dividing a into 1. The result is between 0 and 1. But to my limited knowledge, elliptic curves are integer arithmetic.
The declaration of the Ruby function is
def inverse( a, m = $p)
I don’t know Ruby.
It looks like a is a single variable, and so is m, the modulus value, presumably “the” modulus used in the Bitcoin elliptic curve. Both are integers, not points.
So what really huge concept am I missing?
I am trying to understand the bitcoin arithmetic, as opposed to the mathematics. A couple of websites mention that dividing with the elliptic curve points is impractical so they multiple by the inverse. Just in case it matters my primary reference is this site:
https://learnmeabitcoin.com/technical/cryptography/elliptic-curve/
Trying to stay with the basics, multiply a by the inverse of b is the same as dividing by b. But arithmetically the inverse of a is found by dividing a into 1. The result is between 0 and 1. But to my limited knowledge, elliptic curves are integer arithmetic.
The declaration of the Ruby function is
def inverse( a, m = $p)
I don’t know Ruby.
It looks like a is a single variable, and so is m, the modulus value, presumably “the” modulus used in the Bitcoin elliptic curve. Both are integers, not points.
So what really huge concept am I missing?
Jump to: