I'm working on a small programming project, and I'm struggling a bit with calculating fractions of numbers in a commutative group. I'm by no means a mathematician or a programmer, so please bear with me in terms of terminology and formatting, and let me know if I need to edit my post to make it more understandable. English is also not my first language. I'll focus on the math in this post, and avoid anything programming specific. I would also greatly appreciate if someone could point me in the right direction in terms of formatting questions on this site, specifically with math equations.
Lets say I have a set of numbers composed of integers modulo N, that form an Abelian (commutative) group. N in this case is prime. Addition, multiplication and subtraction operators are easy enough to understand and compute over this group, but I'm running into a few issues when it comes to division.
I know that in order to divide a member of the group by K, I need to calculate the multiplicative inverse of K. I do this by using the extended Euclidean algorithm. After getting the multiplicative inverse of K (denoted K'), I compute:
M * K' mod N
Where M is some integer in the group, and this gives the correct result if M mod K = 0 (M divisible by K). If M is not divisible by K however, I get a rather strange result. Here are a few examples:
N = 104 395 301 (I picked a smallish prime to make it easy to read) K = 3 (the divisor) Multiplicative Inverse of K (K') mod N: K' = 34 798 434 (calculated with extended Euclidean algorithm)
example 1: M = 333:
M * K' mod N
=333 x 34 798 434 mod 104 395 301
=111 (expected result)
example 2: M = 334:
= 334 x 34 798 434 mod N
= 34 798 545
example 3: M = 335:
= 335 x 34 798 434 mod N
= 69 596 979
example 4: M = 336:
= 336 x 34 798 434 mod N
= 112 (expected result)
example 5: M = 337:
= 337 x 34 798 434 mod N
= 34 798 546
example 6: M = 338:
= 337 x 34 798 434 mod N
= 69 596 980
Now, I understand why I get these results, as all of the results are just multiples of K' mod N, which won't ever give me any decimal values like 111.333333... 111.66666... and so forth. But I noticed that when M is not divisible by K, the result is either:
(1 * K') +⌊M / K⌋ (in case of example 2: 34798434 + 111)
or
(2 * K') + ⌊M / K⌋ (in case of example 3: 69596868 + 111)
And since (3 * K') mod N ≡ 0, the result is:
(0 * K') + ⌊M / K⌋ (example 1: 0 + 111)
for any M that is divisible by K .
So the result of any M * K' mod N will be some multiple (n) of K' plus the integer part of M/K:
M * K' mod N ≡ (n * K') + ⌊M / K⌋
I'm finally arriving at my question now. My code needs to find the integer part of M/K. So 111 for examples 1,2,3 and 112 for examples 4,5,6. The key problem is that my code can't tell the difference between 111, K'+111 and 2*K'+111. The reason for this is that these numbers are points on a curve over a finite field (of which the group I'm talking about is a subgroup), and their actual values are obfuscated as a result, while the group operators (multiplication, addition) are still valid. I didn't mention this until now because I'd like to approach this problem without limiting it to a specific curve or finite field, since my code will work with many of them.
I'm looking for a general solution.
Is there a way to separate the integer part of the fraction M/K from the multiple of the multiplicative inverse part when M is not divisible by K?
It is easy to produce all 3 possible solutions with my code (K'+⌊M/K⌋, 2K'+⌊M/K⌋, 3K'+⌊M/K⌋), but I can't figure out how to isolate ⌊M/K⌋ from those three possible solutions.
Values that are "known" to my code are N,K and K'. The input M and the results are "hidden".
Please let me know if any of you can help me understand this, or at least point me in the right direction. Maybe I'm just missing some basic formula or algorithm just because I haven't been using the right keywords while googling.
We are given integers $N$, $K$, and $K'$ such that $KK'\equiv1\pmod N$. Suppose we know $A=MK'\pmod N$. Then we can recover $M$ itself by noting that $AK = MK'K \equiv M \pmod N$. Assuming we know that $0\le M<N$, this specifies $M$ uniquely, and then we can simply use regular division to calculate $\lfloor M/K\rfloor$.