Q:

Given $k, a \in \mathbb{R}$, find a polynomial $P$ such that $P(k) = a$

You are given two real numbers $k,a \in \mathbb{R}$, and you are promised that there is a polynomial with integer coefficients $P \in \mathbb{Z}[X]$ such that evaluating it on $k$ yields $a$, i.e.
Promise: $\ \exists P \in \mathbb{Z}[X] \ \ \ s.t.\ \ P(k) = a$
Problem: find such $P$. In general, I'd expect more than one solution to exist; then I'd be interested in obtaining the one with lowest degree.

Note that $k$ may be any real number, and a particular case of interest (due to context, see below) is $k = -\frac{\sqrt{2}}{2}$.
Some context. I'm a PhD student in computer science and this problem came up in my research when trying to reverse engineer a black box. Essentially, $k$ is a parameter set a priori and $a$ is the output the black box produces; finding $P$ would let me know valuable information about the internal workings of the black box.

I am aware that, if it were the case that $k \in \mathbb{N}$ and $a > 0$, then I could obtain each coefficient of the polynomial by calculating remainders:
$p_0 = a \bmod k$, gives the coefficient of the 0-degree term;
$p_1 = \frac{a - p_0}{k} \bmod k$, gives the coefficient of the 1-degree term, and so on...
$p_2 = \dots$
However the fact that $k$ may be any real number prevents me from using this kind of approach from discrete maths.

A:

If we look just at $k=-\frac{\sqrt2}2$, suppose $P(k)=a$, then $2^Na=p\sqrt2+q$ for $N=\deg P$ and $p,q\in\Bbb Z$, so we can recover some polynomial $P$ just by doing the following:

keep doubling $a$ until it has the form $2^na=p\sqrt2+q$. Take $n$ to be minimal with this property.
since $k^2=\frac12$, we get that $a=p\cdot\frac{\sqrt2}2\cdot\frac1{2^{n-1}} + \frac q{2^n} = -p\cdot k\cdot k^{2(n-1)} + qk^{2n}$ so that the polynomial $P(x)=qx^{2n}-px^{2n-1}$ does the trick and has degree either $2n$ or $2n-1$ (...well, it could have degree $-\infty$ if we started with $a=0$ but I digress)

As for minimality, write $P(x) = \sum_{i=0}^{2n}=c_ix^i$ and note that $a=P(k) = \sum_{i=0}^n\frac{c_{2i}}{2^i} - \sum_{i=0}^{n-1}\frac{c_{2i+1}}{2^i}\sqrt2$ fits into the form $p\sqrt2+q$ after scaling by $2^n$. This is minimal if $c_{2n}$ is odd, and we can ensure that $c_{2n}$ is odd by the minimality of $P$ with $P(k)=a$: indeed, if $c_{2n}=2c_{2n}'$, then $c_{2n}k^{2n} = c_{2n}'k^{2(n-1)}$ using that $k^{-2}=2$, allowing us to reduce $P$ by one degree.
Therefore, the degree of minimal $P$ is twice the minimum $n$ such that $2^na=p\sqrt2+q$, showing that the above algorithm succeeds in finding a minimum-degree $P$ in the case that $a$ arises from an even-degree polynomial. The analysis for odd degree is pretty much the same.
However, this algorithm is fairly ad hoc and is difficult to generalise once $k\neq-\frac{\sqrt2}2$.
I'm not sure how ugly $k$ is allowed to be. For example, if $k$ is transcendental, then $P(k)=a$ will immediately tell you what $P$ is just from trying to represent $a$ in a computable way (relative to $k$, I suppose). In general, I'm not sure how $k$ and $a$ would be  represented, if I'm assuming you are trying to computationally solve for $P$ somehow. For instance, in my above algorithm, I worked under the assumption that the computer was dealing with elements of $\Bbb Q(\sqrt2)$ or something (to ensure the computation is exact).
I'm sure a similar technique to the one above can be used for other $k$ that look "similar to" your case of interest $k=-\frac{\sqrt2}2$, though showing minimality might be more difficult.
Also, if $k\in\Bbb N$, then for any $P(x)\in\Bbb Z[x]$, we would get $P(k)\in\Bbb Z$, so the only $a$ that can be written as $a=P(k)$ would be integers, so the minimal-degree polynomial in this situation is really just the constant polynomial $P(x)\equiv a$. This continues to be the case if $k\in\Bbb Z$, so there's no need to iteratively use modular arithmetic to find $P(x)$.

