MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

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.

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:

Modular inversion $y=x^{-1} \mbox{ mod } p$:

$x y + p m = 1$

Quotient division $q=\lfloor \frac{a}{b} \rfloor$:

$ q b + (a \mbox{ mod } b) t = a$

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

share|cite|improve this question
Both equations have infinitely many solution, and computing the quotient from an arbitrary solution to the latter equation will involve division. In general, we would have $t\equiv 1\pmod{b}$ but not necessarily $t=1$. And for $t\ne 1$, a division by $b$ will be required to reduce it to 1, which is not any better then simply dividing $a$ by $b$. – Max Alekseyev Jul 23 '10 at 17:11
@Speiser: No it is not elementary. I do not want to use extended GCD. In fact, I am in the field of secure multiparty comptuation and I want to implement the GCD algorithm itself in a secure form, given only a secure protocol for modular inversion (Using homomorphic encryption or secret-sharing). It would have been trivial to use extended GCD to solve these equations, but I don't have a secure sub-protocol for that. – M. Alaggan Jul 24 '10 at 0:48
@Alekseyev: Thanks for your useful comment. So since it is not possible I'll try another research direction. – M. Alaggan Jul 24 '10 at 0:49
In the future, you should probably include that kind of information with the original question. It looked a lot like an elementary question. – Qiaochu Yuan Jul 24 '10 at 1:08
@Yuan: Thanks for the hint. I do apologize for the readers who were mislead by this mistake; I am new to online community discussion and the line between not too long and too less information was still a bit fuzzy to me. I just was trying to be nice and write as short as I can so as not to waste the time of the reader. – M. Alaggan Jul 24 '10 at 1:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.