Editing Fibonacci sequence (section)

=== Primality testing ===
The above formula can be used as a [[primality test]] in the sense that if
<math display=block>n \mid F_{n \;-\, \left(\frac{5}{n}\right)},</math>
where the Legendre symbol has been replaced by the [[Jacobi symbol]], then this is evidence that {{mvar|n}} is a prime, and if it fails to hold, then {{mvar|n}} is definitely not a prime. If {{mvar|n}} is [[composite number|composite]] and satisfies the formula, then {{mvar|n}} is a ''Fibonacci pseudoprime''.  When {{mvar|m}} is large{{snd}}say a 500-[[bit]] number{{snd}}then we can calculate {{math|''F''<sub>''m''</sub> (mod ''n'')}} efficiently using the matrix form.  Thus

<math display=block> \begin{pmatrix} F_{m+1} & F_m \\ F_m & F_{m-1} \end{pmatrix} \equiv \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^m \pmod n.</math>
Here the matrix power {{math|''A''<sup>''m''</sup>}} is calculated using [[modular exponentiation]], which can be [[Modular exponentiation#Matrices|adapted to matrices]].<ref>''Prime Numbers'', Richard Crandall, Carl Pomerance, Springer, second edition, 2005, p. 142.</ref>