Title: Why gcd between base point and any other point will give us one or three? Post by: garlonicon on December 29, 2023, 11:19:46 AM First, we start from secp256k1, where we replace the real base point with (x=0x1;y=0x4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee). Then, we calculate "zero side" for the famous equation: y^2=x^3+7. Which means, we move all things to one side, which can give us: x^3-y^2+7=0. The right side is then zero, and the left side is just a huge number, which gives us zero, when we apply modulo p-value. We make sure that our left side is non-negative (so we use x^3-y^2+7 or y^2-x^3-7). Then, this left value is what we can compute for any public key we want. For convenience, we can divide it by p-value, to work with smaller numbers (because all of them are divisible by p-value, if we are working with valid points).
And then, we compare those "zero values" between different public keys, by applying gcd to both of them. If we can get only p-value out of that, we will get just "one" (because of division by p-value), which means this particular pair of points can be present only on this particular curve, or some curve with bigger p-value. However, if our gcd is bigger than one (after dividing by p-value), then it means, we can teleport those points to a different curve, with a different p-value. So, which values can we get out of that? Well, if we start with our modified generator, we can get 0x1, 0x2, 0x4, 0x11, 0x22, 0x44, 0x10c1, 0x2182, 0x4304, and so on. However, if we use the original generator, we can get only 0x1 or 0x3. Why it is the case? Code: basePoint=0x1110df3be5e21e6776516a5fa6702d71d937b2614804cce0315f9575458ff784 Title: Re: Why gcd between base point and any other point will give us one or three? Post by: j2002ba2 on December 29, 2023, 06:40:57 PM Because 0x1110...f784 has many small factors:
2^2 * 17 * 4289 * 6196937 * 9672199247 * 441571470858719851994038335827739586159888848835828007 While 0x1b88...e5e9 has factor 3, and then some unholy big numbers. Your funny random mapping then produces some random integer, which is very very unlikely to have one of the big factors in the second one. That said, what is the purpose of this exercise? Point coordinates are not integers, they are instead infinite sets of all kind of numbers, represented by integers. Specially y^2 = x^3 + 7 does not have integer or rational number solutions. Plugging integers makes even less sense here. Why not use an isomorphic curve of rank>0, i.e. y^2 = x^3 - 2. Then at least you'd know that there are rational solutions, and have a single nice generator (3,5). Title: Re: Why gcd between base point and any other point will give us one or three? Post by: digaran on December 31, 2023, 06:35:12 AM @j2002ba2, can you explain why do we get y= 0x8 when we set x= 0x7, y= 0x8 and k= lambda on secp curve? There was a raccoon around here, he couldn't satisfy me with his answer. Apology for the humor.
|