4 It was too poorly written as indicated in the comments !; added 4 characters in body

I'm in the field of secure multiparty computation using Homomrphic encryption or secret sharing. I am trying 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 $q=\lfloor \frac{a}{b} \rfloor$ by using 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 (i.e. something like $x^{-1} \mbox{ mod } p$)of an encrypted number as a building block for the GCD protocol.

Both

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.

3 typos

I am trying to implement the quotient of division $q=\lfloor \frac{a}{b} \rfloor$ by using modular inversion (i.e. something like $x^{-1} \mbox{ mod } p$).

Both problems can be reduced to solving a linear Diophantine equation.

Modulare

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

2 Edited the title for clarity

1