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

CC BY-SA 4.0
2023-03-02T23:05:39.707Z
I just emailed you the Python code.  Also, this is the link to what I was referring:  https://math.stackexchange.com/questions/1015552/modular-division-for-non-co-prime-numbers?newreg=824023ef82f24eb9b24fb30285c8b698
Alfhilðr ínn Seiðkona
CC BY-SA 4.0
2023-03-02T23:12:26.777Z
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
CC BY-SA 4.0
2023-03-02T21:00:29.233Z
2023-03-02T21:00:29.233Z
Pieter Wuille
<p>Having perused the stackexchange, I found some similar questions, but am having difficulty understanding how to arrive at the solution to  (<em>n</em>-1)*<em>x</em>=1 <em>mod np</em>, where:</p>
<p><em>n:</em> Finite group order of the Bitcoin secp256k1 curve</p>
<p><em>n</em>=115792089237316195423570985008687907852837564279074904382605163141518161494337</p>
<p><em>p:</em> Prime order of the curve</p>
<p><em>p</em>=115792089237316195423570985008687907853269984665640564039457584007908834671663</p>
<p><em>np:</em> (<em>n</em>-1)+(<em>p</em>-1)</p>
<p><em>np</em>=231584178474632390847141970017375815706107548944715468422062747149426996165998</p>
<p>and (<em>n</em>-1) is not coprime to modulo <em>np</em>.</p>
<p>Having performed the following step of <em>np</em>/2 and adding .5 to result one, so as to achieve:</p>
<p><em>F1</em>=115792089237316195423570985008687907853053774472357734211031373574713498083000</p>
<p>Then subtracting the initial result with .5 to achieve:</p>
<p><em>F2</em>=115792089237316195423570985008687907853053774472357734211031373574713498082999</p>
<p>And following instructions from answers to related posts, (<em>n</em>-1) is to be multiplicativeley inversed over <em>mod F1</em> and <em>F2</em>.  However, neither <em>F1</em> or <em>F2</em> are coprime to (<em>n</em>-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.</p>
<p>What steps are required and how are the operations performed to accomplish this?</p>
<p>Thank you.</p>

CC BY-SA 4.0
2023-03-02T14:02:39.760Z
If two numbers *a* and *m* are not coprime, no multiplicative inverse of *a* modulo *m* exists.
Pieter Wuille
CC BY-SA 4.0
2023-03-02T19:03:05.253Z
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
CC BY-SA 4.0
2023-03-03T14:33:14.980Z
So, are you looking for a modular division instead of an inverse?
Murch
CC BY-SA 4.0
2023-03-06T19:36:10.250Z
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
<development><cryptography><secp256k1>
What is the step-by-step algorithmic process to find the modular multiplicative inverse of (n-1) mod np, where (n-1) and np are not coprime?
Alfhilðr ínn Seiðkona
# What is the step-by-step algorithmic process to find the modular multiplicative inverse of (n-1) mod np, where (n-1) and np are not coprime?

(Asked by: username_0 on 2023-03-02)

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.

**Tags:** development, cryptography, secp256k1

> **Comments:**
> **username_1**: If two numbers *a* and *m* are not coprime, no multiplicative inverse of *a* modulo *m* exists.  
> **username_0**: 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.  
> **username_2**: So, are you looking for a modular division instead of an inverse?  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_1 on 2023-03-02. Score: 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.

> **Comments:**
> **username_0**: I just emailed you the Python code.  Also, this is the link to what I was referring:  https://math.stackexchange.com/questions/1015552/modular-division-for-non-co-prime-numbers?newreg=824023ef82f24eb9b24fb30285c8b698  
> **username_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.  

---

