-2

Having perused the stackexchange, I found some similar questions, but am having difficulty understanding how to arrive at the solution to (n-1)*x=1 mod np, where:

n: Finite group order of the Bitcoin secp256k1 curve

n=115792089237316195423570985008687907852837564279074904382605163141518161494337

p: Prime order of the curve

p=115792089237316195423570985008687907853269984665640564039457584007908834671663

np: (n-1)+(p-1)

np=231584178474632390847141970017375815706107548944715468422062747149426996165998

and (n-1) is not coprime to modulo np.

Having performed the following step of np/2 and adding .5 to result one, so as to achieve:

F1=115792089237316195423570985008687907853053774472357734211031373574713498083000

Then subtracting the initial result with .5 to achieve:

F2=115792089237316195423570985008687907853053774472357734211031373574713498082999

And following instructions from answers to related posts, (n-1) is to be multiplicativeley inversed over mod F1 and F2. However, neither F1 or F2 are coprime to (n-1). In order to overcome this, it is explained that GCD and CRT are to be used in order to accurately calculate the modular inverse.

What steps are required and how are the operations performed to accomplish this?

Thank you.

Improve this question
4
  • If two numbers a and m are not coprime, no multiplicative inverse of a modulo m exists.
    – Pieter Wuille
    Commented Mar 2, 2023 at 14:02
  • There is a way to achieve the multiplicative inverse as I have seen it done, the professor who achieved it is assisting me, but he is forcing me to figure out the method (it is unpublished, obviously). Also, I did see a Stackexchange answer explaining the method, as well. I have the Python coding for it, but I am trying to reverse engineer it manually.
    – Alfhilðr ínn Seiðkona
    Commented Mar 2, 2023 at 19:03
  • 1
    So, are you looking for a modular division instead of an inverse?
    – Murch ♦
    Commented Mar 3, 2023 at 14:33
  • Yes, I believe that is what I am looking for, as I was not understanding the problem itself. The entirety of the equation I am trying to solve is: (n-1)*x=G.x mod np.
    – Alfhilðr ínn Seiðkona
    Commented Mar 6, 2023 at 19:36

1 Answer 1

Reset to default
1

What you're asking for is impossible.

You're looking for x such that (n-1)x = 1 mod np. However, both n-1 and np are even. It's easy to see that any multiple of n-1 will be even. Thus, any multiple of n-1 modulo np will also be even. However, the right hand side 1 is odd. This is a contradiction, as the left hand side cannot be odd.

Improve this answer
2
  • I just emailed you the Python code. Also, this is the link to what I was referring: math.stackexchange.com/questions/1015552/…
    – Alfhilðr ínn Seiðkona
    Commented Mar 2, 2023 at 23:05
  • 1
    Yes, and the code you mailed me, and the answer in that linked question, does not compute a modular inverse; it doesn't exist. It's solving equations of the form ax = b mod m, and these have only solutions if b is a multiple of gcd(a,m). In your case, b must be even at the very least. The modular inverse, corresponding to the case b=1, is not that.
    – Pieter Wuille
    Commented Mar 2, 2023 at 23:12

Your Answer

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

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