Results 1 to 2 of 2

Math Help - Modular Inversion

  1. #1
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485

    Modular Inversion

    I have another problem from computational number theory.

    Given \alpha_1,\alpha_2,\ldots, \alpha_k\in \mathbb{Z}_n, show how to compute \alpha_1^{-1}, \alpha_2^{-1}\ldots, \alpha_k^{-1} by computing only one inverse and using at most 3k multiplications.

    As with my other problem, I can find faster method than computing each inverse individually, but I can't stay within the multiplication bound. My idea is this:

    Let \beta=\alpha_1\alpha_2\cdots \alpha_k, noting that computing \beta costs k-1 multiplications. Then, we take the inverse: \beta^{-1}=\alpha_1^{-1}\alpha_2^{-1}\cdots \alpha_k^{-1}. If we want to compute, say \alpha_1^{-1}, we compute \beta^{-1} \alpha_2\cdots \alpha_k=\alpha_1^{-1}, which costs k-1 multiplications. The problem is that if k is large enough, doing this procedure for all of the \alpha_i exceeds the limit of 3k multiplications.

    I would appreciate any suggestions for this problem.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by roninpro View Post
    I have another problem from computational number theory.

    Given \alpha_1,\alpha_2,\ldots, \alpha_k\in \mathbb{Z}_n, show how to compute \alpha_1^{-1}, \alpha_2^{-1}\ldots, \alpha_k^{-1} by computing only one inverse and using at most 3k multiplications.

    As with my other problem, I can find faster method than computing each inverse individually, but I can't stay within the multiplication bound. My idea is this:

    Let \beta=\alpha_1\alpha_2\cdots \alpha_k, noting that computing \beta costs k-1 multiplications. Then, we take the inverse: \beta^{-1}=\alpha_1^{-1}\alpha_2^{-1}\cdots \alpha_k^{-1}. If we want to compute, say \alpha_1^{-1}, we compute \beta^{-1} \alpha_2\cdots \alpha_k=\alpha_1^{-1}, which costs k-1 multiplications. The problem is that if k is large enough, doing this procedure for all of the \alpha_i exceeds the limit of 3k multiplications.

    I would appreciate any suggestions for this problem.
    Well your method can technically fit well within the constraint, if we work in integers and rationals rather than in \mathbb{Z}_n. (Although I doubt this is what the question poser had in mind). Consider the integer \beta=\alpha_1\alpha_2\cdots \alpha_k, and further the integer \beta^{-1}\alpha_1\alpha_2\cdots \alpha_k, all of which to obtain takes k multiplications. Now to get any \alpha_i^{-1} requires just a single multiplication of this integer by the rational \frac{1}{\alpha_i}. So we use exactly 2k multiplications which is much "better" than what the problem asked for. I'm curious about better ways to do it though.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Existence of inversion
    Posted in the Geometry Forum
    Replies: 2
    Last Post: May 19th 2010, 02:27 PM
  2. Inversion
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 9th 2010, 11:53 AM
  3. Inversion
    Posted in the Geometry Forum
    Replies: 0
    Last Post: November 28th 2008, 10:30 AM
  4. Please help mee with this laplace inversion
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 11th 2008, 06:36 AM
  5. Mobius Inversion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 26th 2008, 04:42 PM

Search Tags


/mathhelpforum @mathhelpforum