When factoring 999993, p must divide 10002-7. Reducing mod p shows 7 is a residue, hence p is ±1, ±3, or ±9 mod 28. I don't know if this trick is used by any general purpose factoring programs; probably not.
If p is a Fermat prime, 3 is primitive mod p. Recall that p-1 is a power of 2. There are φ(p-1) = (p-1)/2 primitive elements, each a nonsquare. Assuming p > 3, 3 does not divide p or p-1. Thus [3\p] = [p\3] = -1, and 3 is primitive.
If a Fermat number n, with exponent 2h, is not prime, and p divides n, then 2 raised to the 2h is -1 mod p. Take logs in the multiplicative group mod p, and log(2)×2h maps to (p-1)/2. The image contains all but one of the factors of 2 in p-1. This means log(2)×2h+1 contains exactly the powers of 2 in p-1. For h > 1, p = 1 mod 8, and 2 is a square. Thus log(2), relative to a primitive element b, is even. Pull a factor of 2 out and log(sqrt(2))×2h+2 accounts for the factors of 2 in p-1. Therefore p is 1 mod 2h+2.
I tried this for the first few fermat numbers, including 2128+1. The factors are 59649589127497217 and 5704689200685129054721; and each is 1 mod 256. Similarly, 2256+1 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321. And that's enough of that.