look in our example

10^2 mod 6 = (10 mod 6)^2 mod 6 so:

100 % 6 = 4^2 %6

4^2 mod 6 = 4

if we can find a power of nineteen with a small remainder with the number bigger than 19 that is a power that divides the exponent we can use that small remainder to a smaller power mod the number again to figure it out.

A prime with only 6s and 7s as digits:

[code]7677676676677777767677677666676767676766677677677767677677767776776767676667776677667776666676766766777676767666767667776676767776676766776767676766766666666676677776776666777777777777777777777777777777777777777777777777777777 (226 digits)[/code]

Ha!

So far, the best idea in mind is to perform exponentiation according to the prime factorization of 60, in this case:

So, begin with 19^1 mod 3773512084578210152449.

Obtain cube: 6859 modulo 3773512084578210152449

The above, to the 5th power:

6859^5 mod 3773512084578210152449 = 15181127029874798299 mod 3773512084578210152449.

The above, to the 4th power:

15181127029874798299^4 modulo 3773512084578210152449, which is 1 mod 3773512084578210152449.

The test fails for a = 19.

Composite? No.

Primality testing 3273*2^60+1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 7
Special modular reduction using generic reduction x87 FFT length 32 on 3273*2^60+1
Calling Brillhart-Lehmer-Selfridge with factored part 84.51%
3273*2^60+1 is prime! (0.0165s+0.0006s).

.. The only way it's going to be painful to do by hand is if the exponent is prime.

Ex: 10040 * 2^229 + 1.

[QUOTE=3.14159;231339]

.. The only way it's going to be painful to do by hand is if the exponent is prime.

Ex: 10040 * 2^229 + 1.[/QUOTE]

10040 = 2^3*1255

2^3*2^229 = 2^232 the exponent is no longer prime.

For PFGW's trial division switch:

Not enough integers to be used?

For n ≤ 10^9, there should be about 50845000 primes to divide by. PFGW (3.3.6) is only using about 25 million.

Is it just me, or is there something funny going on, yet again?

303*2^6393 + 1 divides 2^(2^6390) + 1. Any links to a list of the known Fermat divisors?

[url]http://www.prothsearch.net/fermat.html[/url]

I downloaded a sieve program that seemed to be nearly evenly matched with NewPGen;

It can be downloaded [URL="http://www.underbakke.com/primes/"]here[/URL].

For k * 2^7500 + 1; sieve limit being 10^10, NewPGen took about 74-76 seconds. TwinGen took about the same amount of time to sieve to 10^10.

However, it can only use b = 2, not generalized bases.

Update: TwinGen > NewPGen when using > 1 threads. No contest there.

4 threads.. Okay; I definitely have a new base 2 sieve. :smile:

However; NewPGen remains for b > 2.

Excellent news, because I can eliminate faster, albeit at the loss of notifying me when a particular p divides a particular k.

Woots. Moving at a mile a minute, so to speak.

I've reached the upper end of the recommended sieve limit; I am at 35153 candidates remaining, and have sieved to 57.92 trillion.

My odds are at 1 in 7242.

I think I'll stop at 60707053457923, where there are about 35090 k's left. My odds are now at 1 in 7233.. Not much of a change.