Let me address a more general question. Let $q$ and $p$ be primes. We can ask whether or not an element $x \in \mathbb{F}_p$ has a $q^{th}$ root, and if so, what are such roots (I'll assume throughout that $x \ne 0$). If $p \not \equiv 1$ mod $q$ then EVERY $x$ has a unique $q^{th}$ root given by $x^{a}$ with $a$ given by $a=\frac{{1 - (p - 1)^{q - 1} }}{q}$. If $p \equiv 1$ mod $q$, then $x$ is a $q^{th}$ root if and only if $x^{\frac{{p - 1}}{q}}=1$ in $\mathbb{F}_p$ and if it has a $q^{th}$ root, it has $q$ of them. If in addition, $p \not \equiv 1$ mod $q^2$, one such root can be given as $x^{b}$ where $b = \frac{{1 - \left( {\frac{{p - 1}}{q}} \right)^{q(q-1)}}}{q}$ and the others are all $q^{th}$ roots of unity times this (I admit there is some choices made even to write this formula down). This unfortunately rules out exactly your case, which is the most complicated one, namely when $p \equiv 1$ mod $q^2$ (for you $q=2$). To my knowledge, in this case, the only way to write down a $q^{th}$ root involves PICKING an arbitrary $y \in \mathbb{F}_p$ which is not a $q^{th}$ power and expressing the answer in terms of this (and the formula becomes a bit messy). So, your question seems to boil down to whether or not there is a "natural candidate" for a non-square in $\mathbb{F}_p$. Of course, you could always take the "smallest" such non-square- but there are other natural choices (e.g. the "largest").

In case you are interested in how to use such a non-$q^{th}$ power $y$ to find the $q^{th}$ root of $x$, here it goes-

WARNING, I'm fairly sure there is an easier way. This is just what I figured out for fun 6 years ago, when I was just learning abstract algebra, and is copied out of my notebook. I'm pretty sure it can be simplified, but, this at least works:

Let $n$ be the largest $n$ such that $q^{n}$ divides $p-1$. Let $$T(X) = x^{ - \left( {\frac{{p - 1}}{{q^n }}} \right)^{q^n \left( {q - 1} \right)} }.$$

The order of this is $q^{m}$ for some $m$ less than $n$. Let $z = y^{\frac{{p - 1}}{{q^{m + 1} }}}$. Let $b$ be the smallest positive integer such that $z^{bq}=T(x)$. Let $l = \frac{{1 - \left( {\frac{{p - 1}}{{q^n }}} \right)^{q^n \left( {q - 1} \right)} }}{q}$.

Then the $q^{th}$ roots of $x$ are given by the formula

$$z^{b(p - 2) + kq^m } x^l $$

with $k$ varying from $0$ to $q-1$.

To see how this works observe that $T:\mathbb{F}_p^{*} \to \mathbb{F}_p^{*}$ is a group hom onto the $q^{n}$th roots of unity, so $T(x)=:u$ is a $q^{n}$th root of unity and $x^{l}$ is the $q^{th}$ root of $x \cdot u$.

NOTE: If $x$ is a $q^{n}$th power, then $T(x)=1$ and the formula $x^{l}$ provides a $q^{th}$ root WITHOUT making a choice for $y$. HOWEVER, this never happens when $q=2$ and $x=-1$ because $\frac{{p - 1}}{{2^n }}$ is always odd hence $-1$ to that power is never $1$ so $-1$ is never a $2^{n}$th power.

Let me address a more general question. Let $q$ and $p$ be primes. We can ask whether or not an element $x \in \mathbb{F}_p$ has a $q^{th}$ root, and if so, what are such roots (I'll assume throughout that $x \ne 0$). If $p \not \equiv 1$ mod $q$ then EVERY $x$ has a unique $q^{th}$ root given by $x^{a}$ with $a$ given by $a=\frac{{1 - (p - 1)^{q - 1} }}{q}$. If $p \equiv 1$ mod $q$, then $x$ is a $q^{th}$ root if and only if $x^{\frac{{p - 1}}{q}}=1$ in $\mathbb{F}_p$ and if it has a $q^{th}$ root, it has $q$ of them. If in addition, $p \not \equiv 1$ mod $q^2$, one such root can be given as $x^{b}$ where $b = \frac{{1 - \left( {\frac{{p - 1}}{q}} \right)^{q(q-1)}}}{q}$ and the others are all $q^{th}$ roots of unity times this (I admit there is some choices made even to write this formula down). This unfortunately rules out exactly your case, which is the most complicated one, namely when $p \equiv 1$ mod $q^2$ (for you $q=2$). To my knowledge, in this case, the only way to write down a $q^{th}$ root involves PICKING an arbitrary $y \in \mathbb{F}_p$ which is not a $q^{th}$ power and expressing the answer in terms of this (and the formula becomes a bit messy). So, your question seems to boil down to whether or not there is a "natural candidate" for a non-square in $\mathbb{F}_p$. Of course, you could always take the "smallest" such non-square- but there are other natural choices (e.g. the "largest").

In case you are interested in how to use such a non-$q^{th}$ power $y$ to find the $q^{th}$ root of $x$, here it goes-

WARNING, I'm fairly sure there is an easier way. This is just what I figured out for fun 6 years ago, when I was just learning abstract algebra, and is copied out of my notebook. I'm pretty sure it can be simplified, but, this at least works:

Let $n$ be the largest $n$ such that $q^{n}$ divides $p-1$. Let $$T(X) = x^{ - \left( {\frac{{p - 1}}{{q^n }}} \right)^{q^n \left( {q - 1} \right)} }.$$

The order of this is $q^{m}$ for some $m$ less than $n$. Let $z = y^{\frac{{p - 1}}{{q^{m + 1} }}}$. Let $b$ be the smallest positive integer such that $z^{bq}=T(x)$. Let $l = \frac{{1 - \left( {\frac{{p - 1}}{{q^n }}} \right)^{q^n \left( {q - 1} \right)} }}{q}$.

Then the $q^{th}$ roots of $x$ are given by the formula

$$z^{b(p - 2) + kq^m } x^l $$

with $k$ varying from $0$ to $q-1$.

To see how this works observe that $T:\mathbb{F}_p^{*} \to \mathbb{F}_p^{*}$ is a group hom onto the $q^{n}$th roots of unity, so $T(x)=:u$ is a $q^{n}$th root of unity and $x^{l}$ is the $q^{th}$ root of $x \cdot u$.

NOTE: If $x$ is a $q^{n}$th power, then $T(x)=1$ and the formula $x^{l}$ provides a $q^{th}$ root WITHOUT making a choice for $y$. HOWEVER, this never happens when $q=2$ and $x=-1$ because $\frac{{p - 1}}{{2^n }}$ is always odd hence $-1$ to that power is never $1$ so $-1$ is never a $2^{n}$th power. In fact, $T(-1)$ will always be $-1$ to an odd number, hence, $-1$, so, this becomes useless as $x \cdot u= 1$.

Let me address a more general question. Let $q$ and $p$ be primes. We can ask whether or not an element $x \in \mathbb{F}_p$ has a $q^{th}$ root, and if so, what are such roots (I'll assume throughout that $x \ne 0$). If $p \not \equiv 1$ mod $q$ then EVERY $x$ has a unique $q^{th}$ root given by $x^{a}$ with $a$ given by $a=\frac{{1 - (p - 1)^{q - 1} }}{q}$. If $p \equiv 1$ mod $q$, then $x$ is a $q^{th}$ root if and only if $x^{\frac{{p - 1}}{q}}=1$ in $\mathbb{F}_p$ and if it has a $q^{th}$ root, it has $q$ of them. If in addition, $p \not \equiv 1$ mod $q^2$, one such root can be given as $x^{b}$ where $b = \frac{{1 - \left( {\frac{{p - 1}}{q}} \right)^{q(q-1)}}}{q}$ and the others are all $q^{th}$ roots of unity times this (I admit there is some choices made even to write this formula down). This unfortunately rules out exactly your case, which is the most complicated one, namely when $p \equiv 1$ mod $q^2$ (for you $q=2$). To my knowledge, in this case, the only way to write down a $q^{th}$ root involves PICKING an arbitrary $y \in \mathbb{F}_p$ which is not a $q^{th}$ power and expressing the answer in terms of this (and the formula becomes a bit messy). So, your question seems to boil down to whether or not there is a "natural candidate" for a non-square in $\mathbb{F}_p$. Of course, you could always take the "smallest" such non-square- but there are other natural choices (e.g. the "largest").

In case you are interested in how to use such a non-$q^{th}$ power $y$ to find the $q^{th}$ root of $x$, here it goes-

WARNING, I'm fairly sure there is an easier way. This is just what I figured out for fun 6 years ago, when I was just learning abstract algebra, and is copied out of my notebook. I'm pretty sure it can be simplified, but, this at least works:

Let $n$ be the largest $n$ such that $q^{n}$ divides $p-1$. Let $$T(X) = x^{ - \left( {\frac{{p - 1}}{{q^n }}} \right)^{q^n \left( {q - 1} \right)} }.$$

The order of this is $q^{m}$ for some $m$ less than $n$. Let $z = y^{\frac{{p - 1}}{{q^{m + 1} }}}$. Let $b$ be the smallest positive integer such that $z^{bq}=T(x)$. Let $l = \frac{{1 - \left( {\frac{{p - 1}}{{q^n }}} \right)^{q^n \left( {q - 1} \right)} }}{q}$.

Then the $q^{th}$ roots of $x$ are given by the formula

$$z^{b(p - 2) + kq^m } x^l $$

with $k$ varying from $0$ to $q-1$.

Let me address a more general question. Let $q$ and $p$ be primes. We can ask whether or not an element $x \in \mathbb{F}_p$ has a $q^{th}$ root, and if so, what are such roots (I'll assume throughout that $x \ne 0$). If $p \not \equiv 1$ mod $q$ then EVERY $x$ has a unique $q^{th}$ root given by $x^{a}$ with $a$ given by $a=\frac{{1 - (p - 1)^{q - 1} }}{q}$. If $p \equiv 1$ mod $q$, then $x$ is a $q^{th}$ root if and only if $x^{\frac{{p - 1}}{q}}=1$ in $\mathbb{F}_p$ and if it has a $q^{th}$ root, it has $q$ of them. If in addition, $p \not \equiv 1$ mod $q^2$, one such root can be given as $x^{b}$ where $b = \frac{{1 - \left( {\frac{{p - 1}}{q}} \right)^{q(q-1)}}}{q}$ and the others are all $q^{th}$ roots of unity times this (I admit there is some choices made even to write this formula down). This unfortunately rules out exactly your case, which is the most complicated one, namely when $p \equiv 1$ mod $q^2$ (for you $q=2$). To my knowledge, in this case, the only way to write down a $q^{th}$ root involves PICKING an arbitrary $y \in \mathbb{F}_p$ which is not a $q^{th}$ power and expressing the answer in terms of this (and the formula becomes a bit messy). So, your question seems to boil down to whether or not there is a "natural candidate" for a non-square in $\mathbb{F}_p$. Of course, you could always take the "smallest" such non-square- but there are other natural choices (e.g. the "largest").

In case you are interested in how to use such a non-$q^{th}$ power $y$ to find the $q^{th}$ root of $x$, here it goes-

WARNING, I'm fairly sure there is an easier way. This is just what I figured out for fun 6 years ago, when I was just learning abstract algebra, and is copied out of my notebook. I'm pretty sure it can be simplified, but, this at least works:

Let $n$ be the largest $n$ such that $q^{n}$ divides $p-1$. Let $$T(X) = x^{ - \left( {\frac{{p - 1}}{{q^n }}} \right)^{q^n \left( {q - 1} \right)} }.$$

The order of this is $q^{m}$ for some $m$ less than $n$. Let $z = y^{\frac{{p - 1}}{{q^{m + 1} }}}$. Let $b$ be the smallest positive integer such that $z^{bq}=T(x)$. Let $l = \frac{{1 - \left( {\frac{{p - 1}}{{q^n }}} \right)^{q^n \left( {q - 1} \right)} }}{q}$.

Then the $q^{th}$ roots of $x$ are given by the formula

$$z^{b(p - 2) + kq^m } x^l $$

with $k$ varying from $0$ to $q-1$.

To see how this works observe that $T:\mathbb{F}_p^{*} \to \mathbb{F}_p^{*}$ is a group hom onto the $q^{n}$th roots of unity, so $T(x)=:u$ is a $q^{n}$th root of unity and $x^{l}$ is the $q^{th}$ root of $x \cdot u$.

NOTE: If $x$ is a $q^{n}$th power, then $T(x)=1$ and the formula $x^{l}$ provides a $q^{th}$ root WITHOUT making a choice for $y$. HOWEVER, this never happens when $q=2$ and $x=-1$ because $\frac{{p - 1}}{{2^n }}$ is always odd hence $-1$ to that power is never $1$ so $-1$ is never a $2^{n}$th power.