# Performing Point Division on secp256k1 Elliptic Curve for odd Integers

I'm exploring elliptic curve cryptography, specifically on the secp256k1 curve. I've come across the concept of point division by integers using scale multiplication, my question is how can I devide a point by $$7$$, Is there a standard method or cryptographic approach to achieve point division on secp256k1 for these non-power-of-2 integers? If so, how would one go about it? If not, what are the constraints or considerations that make it impractical?

Any insights or references would be greatly appreciated. Thank you!

• What is the difference, if divisible than done! Nov 29, 2023 at 7:43
• We have talked about floor division's equality to Dlog. So, if $n+1$ is divisible by you are fine... Nov 29, 2023 at 11:37
• First am not trying to perform floor division, am try to divide $77G$ by an integer $7$ which normally is $11G$, just like $10G$ divide by $2$ equals $5G$. Nov 29, 2023 at 11:43
• Multiply by $7^{-1}$ Nov 29, 2023 at 12:59
• Until when are you going to realize elliptic curve points form groups and they're not real numbers?! Dec 16, 2023 at 8:55

Is there a standard method or cryptographic approach to achieve point division on secp256k1 for these non-power-of-2 integers? If so, how would one go about it? If not, what are the constraints or considerations that make it impractical?

Here's what's happening: multiplying by $$k^{-1}$$ is the inverse of multiplying by $$k$$ (as long as $$k$$ is relatively prime to $$n$$). That is, $$k^{-1}( kG ) = G$$

For $$k=2$$, we always have $$(n+1)/2 = 2^{-1}$$, and because $$(n+1)/2$$ is easy to compute, we just use that.

For larger $$k$$ (say, $$k=7$$), we do have a similar relation $$(zn+1)/k = k^{-1}$$ for some $$0 < z < k$$ (the one that makes $$zn+1$$ divisible by $$k$$), but it might be that $$z \ne 1$$. Alternatively, $$k^{-1}$$ can be computed directly (say, by using the Extended Euclidean algorithm).

The above holds only if $$k$$ is relatively prime to $$n$$. If it is not, then $$k^{-1}$$ won't exist. The action of multiplying by $$k$$ will be noninvertable (that is, we will have points $$A \ne B$$ with $$kA = kB$$), and so the inverting such an multiplication won't be as simple as multiplying another value. However, in the case of secp256k1, this is not an issue ($$n$$ is prime, and so any smaller value will always be relatively prime to it)

ECDSA (of which secp256k1 is a vatiant) is mainly a combination of two mathematical topic: A. Modular Arithmetic and B. Elliptic Curve.

In modular arithmetic (I assume you know basically what this is) if you want to divide, you need to multiply. Forget about point division and focus here:

Let us choose a prime $$p$$ for our example along with a random number $$k$$ in range $$[1, p-1]$$ and say $$k/n = h$$

So here are our variables: $$p = 13$$, $$n = 2$$ and $$k = 8$$

Now in simple arithmetic, to calculate $$k/2$$ you will do the following:

$$h = 8/2$$

$$h = 4$$ ...$$(1)$$

But in modular arithmetic you would first calculate: $$n^{-1}$$ such that $$n^{-1}*n = 1 ({mod}$$ $$p{)}$$ and then multiply the given number by $$n^{-1}$$ as follows:

$$n^{-1} = 7$$ as $$7*2 = 14$$ and $$14$$ $$({mod}$$ $$13{)}$$ = 1\$

Now in modular arithmetic,

$$h = k/n$$ would become $$h = k*n^{-1} ({mod}$$ $$p{)}$$

Hence, $$h = 8*7 = 56$$

$$h = 56 ({mod}$$ $$13{)} = 4$$ ...$$(2)$$

See both $$(1)$$ and $$(2)$$ matches.

Now Coming to second part: 'Point division', well such thing does not exist, what alone exist in ECDSA is 'point addition' and 'point doubling'. But we know that ECDSA work on principle of modular arithmetic.Hence we can import those properties here.

You want to divide $$77G$$ with 7 then just do it:

calculate inverse modulo of $$7$$ which would be (n = 7)

$$n^{-1} = 33083454067804627263877424288196545100810732651164258395030046611862331855525$$

calculate

$$n^{-1}*77$$ $$({mod}$$ $$p{)}$$

$$= 33083454067804627263877424288196545100810732651164258395030046611862331855525*77$$ $$({mod}$$ $$p{)}$$

$$= 2547425963220956299318561670191133972762426414139647896417313589113399552875425$$ $$({mod}$$ $$p{)}$$

$$= 11$$ $$({mod}$$ $$p{)}$$ [Here p is very large prime number, order]

Now calculating public key for this $$n^{-1}*77(G) = 11G$$

And after all here is a snippet of my code:

 >>>x = 77
>>>a = scalar_mult(x, curve.g)
>>>inverse = im(7)
>>>b = scalar_mult(11, curve.g) <------ the actual expected key
>>>print(scalar_mult(inverse, a)) <------- the actual calculated key
(53957576663012291606402345341061437133522758407718089353314528343643821967563, 98386217607324929854432842186271083758341411730506808463586570492533445740059)
>>>print(b)
(53957576663012291606402345341061437133522758407718089353314528343643821967563, 98386217607324929854432842186271083758341411730506808463586570492533445740059)


See how both keys matches.