dorsal/arxiv
View SchemaClassical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation
| Authors | Alexander Russell, Igor Shparlinski |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0212016 |
| URL | https://arxiv.org/abs/quant-ph/0212016 |
Abstract
We consider the problem of recovering a hidden monic polynomial f(X) of degree d > 0 over the finite field F of p elements given a black box which, for any x in F, evaluates the quadratic character of f(x). We design a classical algorithm of complexity O(d^2 p^{d + c}), for any c > 0, and also show that the quantum query complexity of this problem is O(d). Some of our results extend those of Wim van Dam, Sean Hallgren and Lawrence Ip obtained in the case of a linear polynomial f(X) = X + s (with unknown s); some are new even in this case.
{
"annotation_id": "f3939c8b-a241-4c74-95a3-60f0da20c32d",
"date_created": "2026-03-02T18:01:55.786000Z",
"date_modified": "2026-03-02T18:01:55.786000Z",
"file_hash": "b12d217da401430245c03703494e303d5cb02d02880ceecb425486ad9a6cc053",
"private": false,
"record": {
"abstract": "We consider the problem of recovering a hidden monic polynomial f(X) of\ndegree d \u003e 0 over the finite field F of p elements given a black box which, for\nany x in F, evaluates the quadratic character of f(x). We design a classical\nalgorithm of complexity O(d^2 p^{d + c}), for any c \u003e 0, and also show that the\nquantum query complexity of this problem is O(d). Some of our results extend\nthose of Wim van Dam, Sean Hallgren and Lawrence Ip obtained in the case of a\nlinear polynomial f(X) = X + s (with unknown s); some are new even in this\ncase.",
"arxiv_id": "quant-ph/0212016",
"authors": [
"Alexander Russell",
"Igor Shparlinski"
],
"categories": [
"quant-ph"
],
"title": "Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation",
"url": "https://arxiv.org/abs/quant-ph/0212016"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b657b2e9-8dae-4b3b-9fd3-0e40bb3d8b28",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}