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?
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?