Factors of integers of the form $k^2-k+1$

Question

Factorisation of arbitrary integers is of course a computationally hard problem.

But what if the integers I'm interested in factorising are all of the form $k^2-k+1$ ? Is there some way to compute the factors of such integers faster than using the general tools used for arbitrary integers (e.g whatever tricks SymPy's factorint throws at things)?

Obviously $k^2-k+1 = (k+\sqrt{k-1})(k-\sqrt{k-1})$ which for $k=10$ gets me the $7$ and $13$ factors of $91$ easily. But for $k=256, k^2-k+1=65281$ it's no use at all and there's no obvious (to me) shortcut to the wanted $97$ & $673$.

Is there anything can be done? I have a vague idea there ought to be some connection to quadratic Diophantine equations and thereby the Pell equation and continued fractions...

Answer 1

Bunyakovsky conjectured that any polynomial $p(x)$ with integer coefficients that has the following properties takes infinitely many prime values:

1. The leading coefficient of $p(x)$ is positive.
2. $p(x)$ is irreducible over $\mathbb Z$.
3. The set of numbers $\{p(n)\,:\,n\in\mathbb N\}$ does not share a common factor greater than $1$.

It's easy to see that your polynomial satisfies all three of these constraints. But Bunyakovsky's conjecture is still just a conjecture: I think you'll have a hard time saying anything about prime factors of integers of the form $k^2-k+1$.