0

First of all, just to note that I am having trouble with this MOD math, so for some this question might be basic, but in my case it caused a lot of confusion.

Just for the context. In my previous question Pieter Wuille and I had a discussion in the comments (we've deleted them so you won't find them anymore) about points in a finite field and he said that it's just a convention to represent a point as a "direct" value of some field. For example, in a curve where p = 11, the direct values are [0, 1, 2, ..., 10] (I randomly denoted them as a "direct" values). He said that we can represent, for example, value of 3 also as 14, -8 and -19 etc, since using mod 11 on them they all denote the same value and it is just a convention to represent them as "direct" values. I totally agree with that.

He also said that we can do EC arithmetic (addition) with, for example, (3, 9) as well as with (3, -2) or (3, 20) (since -2 mod 11, 9 mod 11 and 20 mod 11 are all the same values) and we will end up with the same point/result after arithmetic operation. What he specifically drew my attention to is the following (I'm paraphrasing): "as long as you realize that the output points whose coordinates differ by multiple of 11 are the SAME POINTS). This seems totally logical to me and I agree with that, but...

What confuses me is that I always end up with the exactly same point regardless of the input point values. For example, in case of (3, 2) + (9, 5) = (8, 2), according to what he says, if I use 14, -8 or -19 in place of 3 it need to end up with some X coordinate that differ by a multiple of 11 to 8. However, I always end up with the (8, 2) regardless of what are the initial coordinates.

I know that the formula for adding points in EC is as follows (taken from here). I have given it as a picture.

enter image description here

Since we work with the EC over finite field, we must take MOD operation into account , so the modificated formulas are as the following (taken from the same site):

enter image description here

Using these formulas I always end up with the exact same point (in my example (8, 2)), regardless of inputs. So there are no points on output whose coordinates differ by a multiple of 11.

I assume that there is something redundant in this formula, which consistently returns values in the set, as I previously referred, of "direct" values. I assume some MOD is redundant, or do I even need any of these MOD (although when I do not use MOD I and up with totally wrong points).

What am I doing wrong? What is redundant in the formula?

Thanks to all!

1 Answer 1

1

My point was that regardless of whether you do a modulo operation or not, you'll end up with the same point - if you treat differences of a multiple of 11 as "identical".

If of course you do a modulo operation, then clearly you cannot end up with a difference of 11 anymore. The modulo operation is exactly what removes all multiples of 11, and maps all field elements to [0, 1, 2, ..., 10].

You have to remember that what you're really calculating is elements of the "integers modulo 11" field. Since computers (and people) can't natively deal with these, we instead represent the field elements as integers. But as pointed out in your earlier question, it does not matter what representation you use as long as the operations keep the same meaning.

In practice, for addition, subtraction, and multiplication, the modulo operation at the end is optional. If you don't, you'll just end up with another representation for the same field element. The same is not true for division and equality checking. Field division is nothing like integer division at all; it requires multiplication with the modular inverse (and again, the modulo reduction after that is optional). For equality checking you must treat a difference of a multiple of 11 as equality.

2
  • Thanks, and just one (out of context) question. Can we have 2 points on EC with the same Y coo?
    – LeaBit
    Nov 13 at 19:13
  • 1
    @LeaBit Yes, 3 in fact. See bitcoin.stackexchange.com/q/120050/208 (but this results only holds for curves with a=0, and when p%3 = 1). Nov 13 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.