Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.