Modular Division Algorithm

Addition, subtraction, multiplication and exponentiation modulo n are no problem.
Division modulo n (often) IS a problem since fractions are not allowed, only integers.

Normally you would calculate the answer to a modular division by calculating the multiplicative inverse of the denominator and then multiply the numerator by that inverse. (everything mod n of course)
This is perfectly okay and works fine.

My question is: is there an algorithm that gives me the answer to a modular division WITHOUT calculating the multiplicative inverse first?
More than that: when you have calculated the answer, you still have no idea what the multiplicative inverse is.

Just to be clear: I'm NOT talking about any sort of brute-force attack. When the numbers involved are big enough, any form of brute-force attack is useless.
I'm talking about a true algorithm: a series of calculations, repeated with different numbers, that necessarily terminates and gives you the correct answer. (just like for example the Euclidean Algorithm is an algorithm)

Does anybody known such an algorithm?

 

I know of no such algorithm. Nor can I say that such a thing would interest me. I can however give you some tips. If this interest you, create one yourself. Use philosophy, creativity, and imagination first. Then use analytical intelligence to implement the idea. Good Luck!

P.S. You ask a wonderful question!

 

My dear friend Logic,

I am curious if you have made in progress in the creation of your algorithm? Have you tried a philosophical approach yet? Have you tried asking your question on mathematics stack exchange? It is perhaps the most "official" math site you can find.

Continued wishes of Good Luck!

 

Yes, there is an algorithm known as the Extended Euclidean Algorithm which can be used to find the modular inverse of a number without directly calculating it. This algorithm not only gives you the modular inverse but also allows you to calculate it efficiently.

Here's how the algorithm works:

1. Start with the two numbers you're interested in, let's call them a and n, where a is the number you want to find the inverse of, and n is the modulus.
   
   
2. Apply the standard Euclidean Algorithm to find the greatest common divisor (gcd) of a and n. This will give you the gcd as well as two coefficients x and y such that ax+ny=gcd(a,n).
   
   
3. If the gcd of a and n is not 1 (i.e., they are not relatively prime), then a does not have a modular inverse modulo n.
   
   
4. If the gcd is 1, then a does have a modular inverse modulo n. The coefficient x obtained from the extended Euclidean algorithm is the modular inverse you seek. However, to ensure that the result is positive and within the range [0,n−1], you may need to take the result modulo n.
   

This algorithm provides an efficient way to find the modular inverse without explicitly calculating all the multiplicative inverses.


Grasping the fundamentals is not so easy. It require a lot of practice with samples and assignments. I would suggest you to visit Maths assignment Help websites for their samples and assignment solution. You can also contact them at +1 (315) 557-6473.

 

Dear Robert,

Thank you for your reply.

I know the Extended Euclidean Algorithm.

But my question was: is there a way to do modular division WITHOUT calculating the multiplicative inverse (or modular inverse) first.
So that means NOT using the EEA or any other way (there are multiple) to calculate the inverse.

The challenge is this: calculate the answer to a modular division with 2 restrictions:
1) you're NOT ALLOWED to calculate the modular multiplicative inverse and use that
2) you're NOT ALLOWED to do a brute force attack

You ARE ALLOWED to apply the Euclidean Algorithm to check if a division is possible in the first place, but you are NOT ALLOWED to use the EXTENDED Euclidean Algorithm to calculate the multiplicative inverse. (see restriction 1)

Can you do it?

 

Well done Logic, you see now what kindness can do for you?