Modular Division Algorithm

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

  1. Logic

    Logic

    Joined:
    Aug 24, 2023
    Messages:
    12
    Likes Received:
    10
    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
    #1
    conway likes this.
  2. Logic

    conway

    Joined:
    Nov 28, 2023
    Messages:
    77
    Likes Received:
    4
    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!
     
    conway, Jan 3, 2024
    #2
  3. Logic

    conway

    Joined:
    Nov 28, 2023
    Messages:
    77
    Likes Received:
    4
    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!
     
    conway, Mar 18, 2024
    #3
  4. Logic

    ROBERTMILLS

    Joined:
    Feb 27, 2024
    Messages:
    3
    Likes Received:
    1
    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.
     
    ROBERTMILLS, Mar 19, 2024
    #4
    conway likes this.
  5. Logic

    Logic

    Joined:
    Aug 24, 2023
    Messages:
    12
    Likes Received:
    10
    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?
     
    Logic, Mar 19, 2024
    #5
    conway likes this.
  6. Logic

    conway

    Joined:
    Nov 28, 2023
    Messages:
    77
    Likes Received:
    4
    Well done Logic, you see now what kindness can do for you?
     
    conway, Mar 19, 2024
    #6
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.
Loading...