Topic: modular inverse in bitcoin arithmetic (Read 308 times)

Hello vjudeu,
You answered several questions, thank you.
I was not planning on graphing with the GUIs, just displaying a few iterations and some of the intermediate values.  For example, when I set k, which I find to be the private key, to a few low values such as 2 and 4, then walk through to get the public address.
I checked Sage and it looks good.  There are also a few sites that do the specific calculations on line, such as private to public.  I will use them also.

Next step is to install both Ruby and Python and code a few modules in each to see how they feel.  Maybe just code up a GUI and display a few numbers to get that feel.

So, again, thank you,
And thank you to everyone in the thread for your time and patience.

Just an interesting side note:  I read and see for myself how nasty so many interactive forums get, such as X.  Part of it is the anonymous concept.  But in forums like this, everyone is so incredibly helpful and courteous.  That former part of human nature is really disappointing and often discouraging.  But this part of human nature, here, displayed to just small audiences, is quite encouraging.
Thank you again for your kindness.

Yes, they both have unlimited integers.

It is hard to graphically express enormously big curves. Here are all of them, meeting y^2=x^3+7 equation, up to 1000: https://github.com/vjudeu/curves1000/tree/master/png

For example, if you have p=967 from Garlo Nicon's examples, then you have this: https://raw.githubusercontent.com/vjudeu/curves1000/refs/heads/master/png/967.png

You can pick any language you want. Also, if you just want to explore basic things, then curves up to 32-bit should be sufficient, so you can use any language, even C/C++, because it will take some time, to know enough, to work with bigger curves correctly.

Example 32-bit curve: p=0xfffff9af, n=0xfffe390b, base=(0x1,0x3cad5d2d)

Also, Sage is your friend: https://sagecell.sagemath.org/
And then, you have two points, for example (0x1,0x3cad5d2d) and (0x3,0x43f09f34). If you can't get the private key here, then you won't succeed with bigger curves, so you should start with this 32-bit curve, or smaller, and get familiar with them first.

Great advise. I will do that.

---

Received the book and started it.  Thank you.
But, need some advice.  Almost all the web pages I find about bitcoin and the curve have examples in Ruby.  The book uses Python.  In none of the examples online and so far in the book, nothing is said about working with very long numbers.  So I presume that is trivial to both languages.  Is this correct?  I will want to use some simple GUIs to help me understand what I am going.

Should I use Ruby per all the web pages, or Python per the book.  The book is probably more comprehensive than the web page but I don't know.

When it comes to addition and subtraction, then you can apply that to any two public keys. However, if you have multiplication and division, then you can only multiply or divide a public key by a private key. You cannot divide or multiply two public keys alone, here is why: https://bitcointalksearch.org/topic/why-point-by-point-multiplication-is-undefined-in-ecdsa-5460766

So, I guess the way forward for you, would be to test everything on a small elliptic curve, where you can brute force everything. And then, switch to a little bit bigger one. And so on, and so forth. Example parameters: https://bitcointalksearch.org/topic/smaller-elliptic-curves-y2-x37-based-on-secp256k1-5459153

Re:  I think you are taking things way too literal ....

I think you are right. And easier said than done.  Song's bitcoin book arrived.  Working that and read about mathematical groups and fields.

Thanks for your time and patience.

I think you are taking things way too literal, instead of first reading up on what's a group and a field.

You are thinking too much in terms of real numbers, or rather rational numbers, which has nothing to do with modular arithmetics.

Let me give you another example: the natural numbers set: 1, 2, 3, 4, ... infinity

Now, how exactly would you divide 3 by 7? It is undefined, because no value can ever have an inverse in regards to multiplication.

Similarly, you won't be able to subtract 2 from 6, because there is no such thing as "- 2" to add to 6, since no value has an opposite in regards to addition.

So the point is: Natural numbers are not even a group, even though you may be able to define addition and multiplication. Why? Because a group requires every element to have an inverse in regards to the group's operation definition.

Let's "fix" the issue: take integral numbers: -inf, ... -2, -1, 0, 1, 2, ... inf

Wow! Now we have a group, because we every element has an inverse (- x)

Now we can do 6 - 2, progress!

But we're still stuck at 3 / 7, because not every element has a multiplicative inverse, so there is no element in our group that can be multiplied by 7 so that it ends up as the value 1.

Now, we can "fix" this by taking rational numbers: every pair of a / b such that a and b are integral numbers.

Great, progress, now every fraction a / b that you can think of has an inverse = b / a

Now you can do 3 / 7, and it's in the field because a = 3 and b = 7 so this is the simplest form in which it exists already.

So now we have a field. Unfortunately, this is an infinite field of fractional numbers, which has nothing to do with modular arithmetic, because we took things way too far simply when we introduced negative numbers.

To be even more cruel, we took things too far simply by assuming there is a natural order of 1, 2, 3, 4 ....

A modular group is built on other principles, and the elements are not even sequential, they are just unique in such a way to respect some properties, mainly a prime order such that every element has a guaranteed additive inverse. Similarly, a field will also guarantee a multiplicative inverse. The sequence will usually look random, but it has clear build-up rules, some of them old of 400 years.

Those are "eaten" using number theory concepts, prime numbers theorems, and so on, not with real numbers algebra / arithmetic.

So, next time when you read "group" or "field" remember that they may be defined with totally different operations than "normal" addition or multiplication.

Points on a ECC curve are not "added" by their coordinates, it is an "geometric addition" using intersections between lines and the curve's shape, not by adding x or y together and calling it a day.

If I give you a group of emoji elements, my rules for "addition" might involve complex facial characteristics of the colors and symbols of the two emojis, to end up as the addition result. Same way for ECC points.

Garlonicon: great reply.  Thank you

To you and kTimesG:

First, kTimesG, thoughtful moniker.

Above all: With Bitcoin, and other such concepts, rules, required, and allowed operations are important.  Following the rules, regardless of origin and their cause, is what makes bitcoin work.

And recognizing my low knowledge of mathematics, I still have questions.

Looking at the equations, they all use addition.  Addition cannot be directly applied to a point on the curve.  The equation of y^2 = x^3 + 7 makes it impossible.  However, addition can be applied to the constituent parts of the points.  In my thoughts, that differentiation between the points and the constituent parts of the points is critical.  I recognize it may be wrong, but it seems correct.  At least right now.

Addition is nothing more than a short cut to counting.  I have learned that 4 + 4 is eight.  But it is a shortcut for counting.  To make my point,  4 plus 1 is 5, plus 1 is 6, etc.

What is subtraction?  Once at 6, I can subtract 2, then again, and get back to 4.  Subtraction is nothing more than discovering what I can add 2 to in order to get 6.  If addition is allowed, then subtraction is definitely valid.

What is multiplication?  It is nothing more than addition repeated a specified number of times.  I can add 2 to itself, then do it again, and again, and get 6.  Multiplication is nothing more than a shortcut for repeated addition. 

What is division.  Divide 6 by 2 to get 3.  It is nothing more than a shortcut to determine how many times to add 2 to itself to get 6.  Same for multiplication.  If we can add, then we can divide.

If we have addition, then it does follow to say that, by the definition of the words and the operations, there is subtraction, multiplication and division.  But to be redundant, they cannot be applied directly to points on the curve, but to their constituent parts to produce the result desired.

Re: There is no concept of "non-integer" in modular arithmetic. Actually, you shouldn't even think at integers, you can think as modular arithmetic as a set of ordered emoji (or fruits) as its elements. Division is not prohibited - it's simply non-existent, …

As described above, I have some difficulties with that.  If we can add, then we can subtract.  If we can add more than once, then we can multiply.  If we can subtract and multiply then we can divide.

But, and this is huge, and a bit redundant, if the rules of Bitcoin state that we must replace divide by modular inverse, then we must do that.  Otherwise we will never succeed at the task.

That said, I do recognize that you guys know far more than I.  I took Calculus 1 a second time to get an A.  For Calculus II, that semester it was the only course I took, I studied every night, got nothing less than 95 on all the homework, but never got higher than 80 on the tests.  That gave me the B needed to graduate.  So, I am not good with mathematics, but am relatively good with arithmetic.  Got an A in statistics without much problem.  And all that, because, given their huge and increasing place in world society, I want to have a reasonably good understanding in how Cryptos work

I will dig into the concepts of Group, Field, etc.  I do solicit suggestions of where to look.

Thank you again for your time and patience.

There is no concept of "non-integer" in modular arithmetic. Actually, you shouldn't even think at integers, you can think as modular arithmetic as a set of ordered emoji (or fruits) as its elements. Division is not prohibited - it's simply non-existent, what you have is multiplication only. If the intent is to find some element by which you multiply to end up at the neutral element, this is what you would call "division". You can only use the tools offered by the structure.

Why not start off with the basic definitions of a Group, Field, prime field, before diving deep into elliptic curves (which are cyclic additive Groups) defined over some prime +* Field? Else you may get dizzy.

Yes. Which means, that it is reduced into "3x^2/2y".

Because it is reduced into zero, if you compute the derivative:

Division is defined as multiplication by inverse. For example:

More detailed explanation: https://www.coindesk.com/markets/2014/10/19/the-math-behind-the-bitcoin-protocol/

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:

Y² = x³ + ax + b  where a = 0 and b = 7 giving us
Y² = x³ + 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.

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.

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.

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:

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?