Search primes of form 2*n^n ± 1

[rogue]

Originally Posted by Citrix

No optimizations - just testing one candidate at a time and then LLRing it if no factor was found.
The generic FFT made me stop the search as each candidate was taking too long.

Interesting. You basically ran sr1sieve against each individual candidate, then when sieved deeply enough, tested that candidate with llr. I'll consider that with my next revision.

*edit* After some experimentation, I don't think the method I just mentioned is faster. For 2*b^b+/-1 from n=200000 to n=210000 I can sieve with kbbsieve to 1e7 in 83 seconds. There are 1466 terms remaining. Per term sieving to 1e9 with srsieve/sr1sieve takes about 20 seconds. Even if half of those terms are removed between 1e7 and 1e9, that gives at most 8300 seconds for kbbsieve to sieve that range to 1e9. It would take srsieve/sr1sieve at least 15,000 seconds.

[rogue]

Originally Posted by Dr Sardonicus

The behavior of nⁿ (mod p) has some (perhaps) interesting consequences for sieving.

If p == 3 (mod 8), then the multiplicative order m of Mod(-2, p) is odd, and the multiplicative order of Mod(2, p) is 2*m. It follows that the number of residues of n (mod (p-1)*p) for which

2*nⁿ + 1 == 0 (mod p)

is three times the number for which

2*nⁿ - 1 (mod p).

For example, with p = 3,

2*nⁿ + 1 == 0 (mod 3) for n == 1, 2, or 4 (mod 6), while

2*nⁿ - 1 == 0 (mod 3) for n == 5 (mod 6).

If p == 7 (mod 8) the situation is reversed; the multiplicative order m of Mod(2, p) is odd, and the multiplicative order of Mod(-2, p) is 2*m. The number of residues n (mod (p-1)*p) for which

2*nⁿ - 1 -- 0 (mod p)

is three times the number for which

2*nⁿ + 1 == 0 (mod p).

For example, with p = 7,

2*nⁿ - 1 == 0 (mod 7) for n == 2, 4, 10, 23, 25, or 26 (mod 42), while

2*nⁿ + 1 == 0 (mod 7) for n == 5 or 31 (mod 42).

For p == 5 (mod 8), the multiplicative orders of 2 and -2 (mod p) are the same, and the number of residues (mod (p-1)*p) for which 2*nⁿ + 1 and 2*nⁿ - 1 are divisible by p, are the same. For example, with p = 5,

2*nⁿ - 1 == 0 (mod 5) for n == 7 or 13 (mod 20), while

2*nⁿ + 1 == 0 (mod 5) for n == 3 or 17 (mod 20).

For p == 1 (mod 8) the situation is not generally predictable. If however 2 is not a biquadratic residue (mod p), then the numbers of residues (mod (p-1)*p) for which 2*nⁿ + 1 and 2*nⁿ - 1 are divisible by p, will be the same. Unfortunately, determining whether 2 is a biquadratic residue (mod p) isn't cheap AFAIK.

If m is the multiplicative order of 2 (-2, resp) mod p, the number of residues (mod (p-1)*p) for which 2*nⁿ - 1 (2*nⁿ+ 1, resp) are divisible by p are

Take a look at the code and see if you can implement some of these optimizations. Note that k does not need to equal 2 when running kbbsieve.

I also realized today that I can remove some terms due to algebraic factorizations, but haven't coded that yet.

[Citrix]

Originally Posted by rogue

Interesting. You basically ran sr1sieve against each individual candidate, then when sieved deeply enough, tested that candidate with llr. I'll consider that with my next revision.

*edit* After some experimentation, I don't think the method I just mentioned is faster. For 2*b^b+/-1 from n=200000 to n=210000 I can sieve with kbbsieve to 1e7 in 83 seconds. There are 1466 terms remaining. Per term sieving to 1e9 with srsieve/sr1sieve takes about 20 seconds. Even if half of those terms are removed between 1e7 and 1e9, that gives at most 8300 seconds for kbbsieve to sieve that range to 1e9. It would take srsieve/sr1sieve at least 15,000 seconds.

It was faster than PFGW/Multisieve. I did not have kbbsieve several years ago, when I tested it.

[rogue]

Originally Posted by Citrix

It was faster than PFGW/Multisieve. I did not have kbbsieve several years ago, when I tested it.

That makes sense. llr should be able to run with the output from kbbsieve.

[henryzz]

I think that I now understand how to add a form based upon your guide. I am going to try to create a sieve with varying and based upon the xyyx sieve.
Once that is done I may extend it to more than two bases possibly with fixed n. I would imagine that the majority of the work will be in combining the different combinations of and modulo p given enough of them. The speed will probably be proportional to the number of terms remaining.

[Dr Sardonicus]

Originally Posted by rogue

Take a look at the code and see if you can implement some of these optimizations. Note that k does not need to equal 2 when running kbbsieve.

I also realized today that I can remove some terms due to algebraic factorizations, but haven't coded that yet.

I'm afraid me looking at the code would not result in much more than my eyes crossing and glazing over. The formula I concocted will work for k, if m is the multiplicative order of Mod(k, p) [resp Mod(-k,p)], provided of course that the prime p does not divide k. The only (possibly) useful thing the formula tells me is, the primes p giving a (relatively) bountiful harvest of residues mod (p-1)*p, are those for which the multiplicative order of Mod(k,p) is very small. For k = 2, then, Mersenne primes would in a sense do the "best" at sieving out candidates.

Algebraic factors are a great idea. I had had it on my list of things to look at, but hadn't yet come up with any examples...