Modular Division Algorithm

Discussion in 'Number Theory' started by Logic, Aug 25, 2023.

  1. Logic


    Aug 24, 2023
    Likes Received:
    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?
    Logic, Aug 25, 2023
Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.
Similar Threads
There are no similar threads yet.