Is $p$ is square modulo $F_p$ when $p=4k+1 > 5$? $F_n$ are the Fibonacci numbers.
In On computing factors of cyclotomic polynomials p.1 for odd square-free $n>1$ the cyclotomic polynomial $\Phi_n(x)$
satisfies:
$$ 4 \Phi_n(x)=A_n(x)^2 - (-1)^{(n-1)/2} n B_n(x)^2 \qquad (1)$$
and Brent gives algorithm for computing $A_n,B_n$.
For natural $N$, if we know $n$-th root of unity modulo $N$
the LHS will vanish and if $B_n$ is invertible this gives
square root modulo $N$ of $(-1)^{(n-1)/2} n$.
Roots of unity come for free for sequences of the form
$(a^n-1)/(a-1)$ and experiments suggest for composite $n$
non-trivial factor is found (which is known for other reasons)
and for $n$ prime the trivial root is found and $B_n$ is invertible.
For $N=F_p$, $p$ odd prime, work in ($\mathbb{Z}/N\mathbb{Z})[w]/(w^2-5)$.
$(1+w)/(1-w)$ is $p$-th root of unity from the closed form for
Fibonacci numbers.
Experiments suggest that if $p=4k+1$, Brent's algorithm gives solution
in $\mathbb{Z}/N\mathbb{Z}$, i.e. the "algebraic" parts cancels.
if $p=4k+3$, the square root is of the simple form $w \mathbb{Z}/N\mathbb{Z}$,
which gives square root of $-5p$.

Q1 Is $p$ is square modulo $F_p$ when $p=4k+1 > 5$?
Q2 How to explain the cancellation of $w$?

This doesn't hold for composite $p$.
Similar result is possible for Lucas number, where $w$ is known
and probably $\sqrt{-1}$ might appear.
 A: The answer to the first question is yes, although the argument I give below is not along the lines that you were originally thinking. I will show that $p$ is a square modulo $q$ for every prime factor $q$ of $F_{p}$, provided $p \equiv 1 \pmod{4}$ and $p > 5$.
As you mention, $\zeta = \frac{1 + \sqrt{5}}{1 - \sqrt{5}}$ is a $p$th root of unity modulo $F_{p}$ and hence modulo $q$. Also $\zeta$ will lie in either $\mathbb{F}_{q}$ or in $\mathbb{F}_{q^{2}}$. The classical Gauss sum formula allows one to express $\sqrt{p}$ in terms of $\zeta$:
$$
  \sqrt{p} = \sum_{j=1}^{p-1} \left(\frac{j}{p}\right) \zeta^{j}.
$$
Now if $\sigma : \mathbb{F}_{q^{2}} \to \mathbb{F}_{q^{2}}$ is the nontrivial automorphism (given by $\sigma(x) = x^{q}$), we can see that $\sigma(\zeta) = \zeta$ if $\sqrt{5} \in \mathbb{F}_{q}$, and $\sigma(\zeta) = 1/\zeta$ when $\sqrt{5} \not\in \mathbb{F}_{q}$. In the former case, it's clear that $\sqrt{p}$ is fixed by $\sigma$ and hence is in $\mathbb{F}_{q}$, while in the latter case, we have
$$ \sigma(\sqrt{p}) = \sum_{j=1}^{p-1} \left(\frac{j}{p}\right) \zeta^{-j}
= \sum_{j=1}^{p-1} \left(\frac{-j}{p}\right) \zeta^{j} = \left(\frac{-1}{p}\right) \sqrt{p}. $$
Since $p \equiv 1 \pmod{4}$, $\left(\frac{-1}{p}\right) = 1$ and so in this case $\sqrt{p} \in \mathbb{F}_{q}$ also.
