Integer factorization simplification

161 Views Asked by At

I found a small improvement to the brute force algorithm for the Integer Factorization. Please tell me if there is a point to investigate it more or there are better similar ideas.

I found that if you take the first 7 primes:

$$2,3,5,7,11,13, 17$$

Than you traverse over the natural values(that are not composite of those values) from $10^6$ to $10^6 * 2$(This is what I tested). Let those values be $f(n)$.

Now if you look on $f(n+1) -f(n)$, you will find a repeatable sequence in it, with the length of 41284.

Now take an obituary number $N$, find its position in the sequence by doing mode.

Now when you testing if value is composite or not, you can skip all the values from this sequence. It will reduce the number of values that you need to exam by about $8$;

Is my idea original? Can you give me a reference of some similar approaches?

1

There are 1 best solutions below

0
On BEST ANSWER

I think what you're suggesting is wheel factorization using the first seven primes. That technique is well-known and is useful -- though smaller wheels tend to be more efficient in practice. But that wheel has 92160 elements, not 41284.