The following numbers trivially (because of their algebraic form x2-y2=(x+y)(x-y)) factor into two primes of nearly equal size surrounding a power of two. They are RSA-like, but would be terrible for RSA because they are easily factored by Fermat's factorization method.
22 - 0224 - 12
28 - 32
216 - 152
232 - 152
264 - 2672
2128 - 22532
2256 - 58232
2512 - 3572
21024 - 1695752
22048 - 1511372
24096 - 20612672
28192 - 75420632
f(mid)=for(i=0, 10^20, if(ispseudoprime(mid-i) && ispseudoprime(mid+i), answer=i; break)); answer
Sieve methods would tremendously improve performance in finding more bracket primes.
The 256-bit entry takes 8 minutes 32 seconds to factor with Pari/GP, including the futile ECM.
1045±9 takes 5 to 8 hours to factor with the same default settings. What a difference 43 bits makes!
A047160 . By Goldbach's Conjecture, there exist bracket primes around any power of two.
No comments :
Post a Comment