[ylhxaoxg] Easy Sierpinski problem multipliers

Omitting the 70 multipliers known to be difficult (as listed on Wilfrid Keller's page), the remaining exponents for the Sierpinksi problem can be fairly quickly recalculated with Pari/GP.

tough=[2897, 3061, 4847, 5297, 5359, 5897, 7013, 7651, 8423, 10223, 13787, 14027, 16817, 18107, 19249, 20851, 21181, 22699, 24737, 25819, 27653, 27923, 28433, 32161, 33661, 34711, 34999, 36983, 37561, 39079, 39781, 40547, 44131, 44903, 46157, 46187, 46471, 47897, 48833, 49219, 50693, 51917, 52771, 53941, 54001, 54739, 54767, 55459, 59569, 60443, 60541, 62093, 62761, 63017, 64007, 65057, 65567, 67193, 67607, 67759, 69107, 69109, 71417, 71671, 74191, 74269, 75841, 76759, 77899, 78181];
fs(k, nmax)=answer=0;for(n=1, nmax, if(ispseudoprime(1+k*2^n), answer=n;break));answer
mt=[];for(j=0, 78556/2, k=2*j+1;if(!setsearch(tough, k, 0), z=fs(k, 8000);if(z, print(k, " ", z), mt=concat(mt, k))))
time = 4min, 51,630 ms.
[solutions]
? mt
%3 = [78557]

The complete list of solutions may also be useful as a collection of primes of many different sizes.

The Sierpinski problem concerns itself only with odd multipliers because usually the powers of two of an even multiplier can be divided out and added to the exponent. However, the multiplier 2^16 = 65536 is special. The problem of finding a prime number 65536*2^n+1 (n>0) is equivalent to a classic unsolved problem in number theory: are there any Fermat primes larger than 65537?

Unfortunately, the Pohlig-Hellman algorithm makes these primes unsuitable for Diffie Hellman.