Reducing two variable linear Diophantine equation to modular inversion - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T06:05:29Z http://mathoverflow.net/feeds/question/33101 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33101/reducing-two-variable-linear-diophantine-equation-to-modular-inversion Reducing two variable linear Diophantine equation to modular inversion M. Alaggan 2010-07-23T15:41:31Z 2010-07-24T00:56:16Z <p>I'm in the field of secure multiparty computation using Homomrphic encryption or secret sharing. I want to implement a secure protocol to compute the GCD of two encrypted numbers. </p> <p>To calculate the GCD, I particularly need to be able to securely calculate the quotient of the division of two numbers. There is a secure protocol for that but is too expensive. Instead, I thought that I might use the much cheaper protocol for computing the modular inversion of an encrypted number as a building block for the GCD protocol. </p> <p>Since both problems (quotient and modular inversion) can be reduced to solving a linear Diophantine equation then perhaps we can reduce one to the other:</p> <p>Modular inversion $y=x^{-1} \mbox{ mod } p$:</p> <p>$x y + p m = 1$</p> <p>Quotient division $q=\lfloor \frac{a}{b} \rfloor$:</p> <p>$q b + (a \mbox{ mod } b) t = a$</p> <blockquote> <p>The question is whether we can rephrase this equation such that the right hand side is 1 (and still be a linear Diophantine), so we are able to use an existing modular inversion protocol to calculate the quotient division.</p> </blockquote> <p>P.S.: I can't use the extended euclidean algorithm directly on any of them. The only allowed (secure) protocols to be used as building blocks are modular inversion, multiplication, modular division, and addition.</p>