$2^k+3$ : Primality Brute Forcing Theory Below The Square Root

Question

I'm testing a theory of brute forcing $2^k+3$.

I've tried to test $(2^k)+3$ where $k=84$ but my computer just takes too long... Java takes too long too..

It's pretty stupid to assume 83 tests makes a perfect case, but I'll take it as a halfway decent case.

My Brute Force -vs- Square Root Brute Force

• $(2^k)+3$ where $k=55$ as prime in 4.7 seconds vs 7.1 seconds.
• $(2^k)+3$ where $k=64$ as NOT PRIME in 19 seconds vs 29 seconds
• $(2^k)+3$ where $k=67$ as prime in 63 seconds vs 899 seconds.

I'm no expert and I'm sure there are much better ways than brute forcing...

I just found it weird (despite being useless?) and I am not capable of mathematically proving/testing why it works so far as I am not a mathematician - and I am curious if it will continue to work.

For numbers of the form $2^k+3$:

1. Find $2^k+3$.
2. Take the square root of step 1.
3. Take the square root of step 2.
4. Times the result of step 3 by the square of k.
5. Times the result of step 4 by 3.
6. Mod by all numbers underneath step 5.
7. If no result of step 6 equals 0, the number is prime.

Further optimization can include testing step 6 by numbers of form 6k+-1.

Answer 1

to test big number, is better to use a more specialized algorithm than trial division like: Miller-Rabin (deterministic version) or Baille-PSW

here you can find implementations to the Miller test: http://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test and adjusting it with the pseudo primes find in prove2_3.html and StrongPseudoprime you can make this test exact until 1543267864443420616877677640751301 (1.543 x 10³³)