[fixfqzox] Primes with many set significant bits

Search for large n-bit primes p for which the factorization of p-1 is known. Large n-bit primes are of the form 2^n-k for small k << 2^n. When written in binary, they begin with many consecutive 1s. This is vaguely in contrast to primes of the form k*2^n+1, which have a lot of zero bits and p-1 is also easy to factor.

First idea is to use the algebraic factorization p-1 = 2^n-a^2 = 4*(2^v+b)*(2^v-b) where v = n/2-1, b = a/2. Test for primality of the factors, and we get primes 2^n-a^2+1 for the following selected (n,a): (4, 0); (8, 10); (16, 42); (32, 3090); (64, 7722); (128, 67290); (256, 559398); (512, 12469218); (768, 21765282); (1024, 2652078); (1280, 103509018); (1536, 374122770); (1792, 73035570); (2048, 152517702).

Previous different attempts, including safe primes which are probably the"right" way to go.

Second idea is to take for granted that all 256-bit numbers are "trivial" to factorize (even 2^256-5823^2 factorizes in 9 minutes without taking advantage of its algebraic structure), so search for numbers of the form p = 1+2^(n-256)*(2^256-i). This gives us primes for the following (n,i): (256, 190); (512, 105); (768, 163); (1024, 229); (1280, 108); (1536, 595); (1792, 195); (2048, 18); (2304, 174); (2560, 2728); (2816, 859); (3072, 601); (3328, 201); (3584, 1318); (3840, 174); (4096, 1933); (4352, 1254); (4608, 2700); (4864, 268); (5120, 420); (5376, 1204); (5632, 2548); (5888, 709); (6144, 796); (6400, 2920); (6656, 865); (6912, 6973); (7168, 1476); (7424, 6969); (7680, 1611); (7936, 333); (8192, 9240); (8448, 2044); (8704, 5355); (8960, 514); (9216, 2299); (9472, 2814); (9728, 1509); (9984, 411); (10240, 6330); (10496, 2098); (10752, 1890); (11008, 3394); (11264, 513); (11520, 3358); (11776, 3183); (12032, 2385); (12288, 8395); (12544, 5380); (12800, 1419); (13056, 2701); (13312, 5628); (13568, 18001); (13824, 4125); (14080, 20134); (14336, 7845); (14592, 5098); (14848, 4018); (15104, 634); (15360, 19186); (15616, 3991); (15872, 471); (16128, 454); (16384, 5563); (16640, 448); (16896, 4158); (17152, 8908); (17408, 3406); (17664, 3690); (17920, 2028); (18176, 5076); (18432, 5131); (18688, 9333); (18944, 330); (19200, 3313); (19456, 5559); (19712, 4816); (19968, 3673).