My question was closed on Theoretical computer since.
May I publish the modified version of it here?
I am working on Integer Factorization problem, and I came to idea of applying Fermat's sieving improvement in multiplication.
Let it be $N$ the value we want to factor, such that $$N = ab$$
Now I want to take a small prime value $k$ and find all the possible values of $a$ such that: $$(a\mod k)(b\mod k)=N\mod k$$
This will allow me to find the factors of $N$ by using the next algorithm
set 'options' as a group of all the values of a as described above while i smaller than N do while j smaller than options length do test if i*k + options[j] is a factor, in case it is, finish and print it set j to j + 1 end while loop set i to i + k end while loop
But it doesn't stops here, next I want to take the next prime value after $k$, let it be $l$, find it's group of optional values of 'a', and merge it with the 'k' group, using the next algorithm
return all the shared values of j and l groups over jl cycle
The problem is that I don't know if applying the factory algorithm on 'l' group will find the factor $a$ or $b$, so I can't know for sure if the merged group will find the factor $a$
For the next input
- $N$ - big integer with only two non trivial factors.
- $k, l$ - two small primes
I want to get the next output
- a group of integers between 0 - $kl$ that has less than $kl$ values and can be used in my factory algorithm to find the factors of $N$, the group should be created using the merge as described above.