$F\_n$ are the Fibonacci numbers.


In [On computing factors of cyclotomic polynomials p.1](http://arxiv.org/abs/1004.5466) 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.



Is $p$ is square modulo $F_p$ when $p=4k+1 > 5$?
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.


