Solution

Compose the two constructions in part (d) to obtain

U_{g} = U_{f_{2}} U_{f_{1}}, g (x) = f (x + 1) - f (x),

using two queries to

U_{f}

. For

f (x) = a x^{2} + b x + c

over

Z_{3}

g (x) = a (2 x + 1) + b = 2 a x + (a + b) .

This is affine with slope

s_{g} = 2 a = - a

. Apply the one-query affine procedure from part (c) to the implemented oracle

U_{g}

. It returns

s_{g}

with certainty, after which the fixed classical computation

a = 2 s_{g} (mod 3)

recovers the quadratic coefficient. Since one use of

U_{g}

consists of one use each of

U_{f_{1}}

and

U_{f_{2}}

, the algorithm makes exactly two calls to the original oracle

U_{f}

 Ancestors (11)

There are no discussions about this article yet.

There are currently no matching articles.