# Learning a single-variable polynomial, or the power of adaptive queries

DevFeed: [Learning a single-variable polynomial, or the power of adaptive queries](<https://devfeed.tech/articles/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries-40370.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/>)

Published: 2014-11-18T09:00:18Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Computing](<https://devfeed.tech/topics/computing.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Query (disambiguation)](<https://devfeed.tech/topics/query.md>)

Tags: [adaptive-queries](<https://devfeed.tech/tags/adaptive-queries.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [github](<https://devfeed.tech/tags/github.md>), [implementation](<https://devfeed.tech/tags/implementation.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [number-theory](<https://devfeed.tech/tags/number-theory.md>), [polynomial-identity-testing](<https://devfeed.tech/tags/polynomial-identity-testing.md>), [polynomial-interpolation](<https://devfeed.tech/tags/polynomial-interpolation.md>), [polynomials](<https://devfeed.tech/tags/polynomials.md>)

## AI overview

This tutorial shows how adaptive queries can recover a secret single-variable polynomial with nonnegative integer coefficients using only two queries: p(1) and p(p(1)+1). It explains how modular arithmetic extracts the coefficients and contrasts this with the larger number of non-adaptive queries required by polynomial interpolation.

## Source excerpt

Problem: Alice chooses a secret polynomial $ p(x)$ with nonnegative integer coefficients. Bob wants to discover this polynomial by querying Alice for the value of $ p(x)$ for some integer $ x$ of Bob's choice. What is the minimal number of queries Bob needs to determine $ p(x)$ exactly? Solution: Two queries. The first is $ p(1)$, and if we call $ N = p(1) + 1$, then the second query is $ p(N)$.