Thread for posting tiny primes

[science_man_88]

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.

[3.14159]

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

7677676676677777767677677666676767676766677677677767677677767776776767676667776677667776666676766766777676767666767667776676767776676766776767676766766666666676677776776666777777777777777777777777777777777777777777777777777777 (226 digits)

Ha!

[3.14159]

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.

[science_man_88]

Originally Posted by 3.14159

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

Ex: 10040 * 2^229 + 1.

10040 = 2^3*1255

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

[3.14159]

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?

[3.14159]

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

[axn]

http://www.prothsearch.net/fermat.html

[3.14159]

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

It can be downloaded here.

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.

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.

[3.14159]

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

[3.14159]

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.

[3.14159]

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.