If you had a fast method for solving Pell equations $x^2 - dy^2 =1$, you can factor numbers $N$ quickly: all you have to do is compute gcd$(x-1,d)$ for $d = N, 2N, 3N, \ldots$ until
you find a factor; if the factor is not prime, repeat the procedure.
Schoof showed that you don't have to know the actual solution of the Pell equation, but that the size of the regulator is sufficient. His method uses Shanks' idea of infrastructure
(see e.g. Jacobson and Williams, Solving the Pell Equation). By computing an ambiguous ideal
(if the norm of the fundamental unit is positive) he can then factor $d = N$; if the ambiguous ideal is trivial, do the same for $d = 3N$ etc.
Of course you cannot expect to factor Fermat numbers by simply writing down a solution of
the corresponding Pell equation. In the early days of factoring in the 1970s, Brillhart
and Morrison suggested using small multiples of $N$ if the period of the continued fraction of $\sqrt{N}$ is too small - this hasn't changed.
Just to confirm your list of $t[2]$ and extend it a bit, here is what
those terms look like:
$t[2]=$
$$
4,8,12,16,24,30,32,40,50,64,78,90,104,108,128,140,156,176,192,208,216,234,250,256,280,304,320,338,350,374,392,420,440,468,486,500,512,540,570,598,630,648,676,704,726,750,768,800,832,858,882,910,950,972,1008,1024,1056,1088,1122,1150,1176,1210,1248,1280,1296,1344,1372,1426,1458,1500,1536,1568,1584,1600,1632,1672,1694,1728,1760,1792,1824,1856,1904,1936,1976,2016 \;.
$$
Best Answer
If N is a prime power it is of the form $p^i$ where $i \leq \log_2(N)$. One can thus compute each of the first $\log_2(N)$ roots of $N$, and test if the resulting number is (first an integer) and then if it is a prime using the AKS algorithm (although perhaps Shor meant to use a randomized test, such as Miller–Rabin, as the paper pre-dates AKS). Obviously if $N$ is a prime power this will produce the factorization.