Background
I made another improvement to Fermat's sieve factorization, by merging the sieves groups of $4,3,5,7,11,13,17$ in two one big group.
This method allows me to reduce the values that I need to check by $100$ to $1000$. Each number you are factoring gives different results.
Goal
I want to take it to the next level and apply this idea on regular multiplication.
Idea
Lets assume that the value we want to factor is $N$
$$N=ab$$
Next I will pick up a small prime number $k$ , and calculate $m$: $$m=N\mod k$$
Next I will find the group of values that by multiplying them and applying mod $k$ we will get the result of $m$
Now in order to factor $N$ all I need to do is to check all those value in a cycles of $k$ and I will find its factors.
Here is a small java implementation of this idea
public class SimpleFactor {
private static final BigInteger ZERO = BigInteger.valueOf(0);
private static final BigInteger ONE = BigInteger.valueOf(0);
public void factor(BigInteger cycle, BigInteger input) {
ArrayList<BigInteger> options = sieve(cycle, input);
MAIN: for (BigInteger x = ZERO; x.compareTo(input) < 0; x = x.add(cycle)){
for (BigInteger bigInteger : options) {
BigInteger testedValue = x.add(bigInteger);
if(input.mod(testedValue).equals(ZERO)){
if(testedValue.equals(ONE)){
continue;
}
System.out.print("Got it: " + testedValue);
break MAIN;
}
}
}
}
private ArrayList<BigInteger> sieve(BigInteger mod, BigInteger input){
ArrayList<BigInteger> newOptions = new ArrayList<BigInteger>();
BigInteger inputMod = input.mod(mod);
HashMap<BigInteger, Object> map = new HashMap<BigInteger, Object>();
for (BigInteger i = ZERO; i.compareTo(mod) < 0; i = i.add(ONE)) {
for (BigInteger j = i; j.compareTo(mod) < 0; j = j.add(ONE)) {
if(i.multiply(j).mod(mod).equals(inputMod)){
if (map.put(i, i) == null) {
newOptions.add(i);
}
break;
}
}
}
return newOptions;
}
}
Question
Let $N$ be the number we want to factor, such that
$$N = ab$$
My problem is that when I am getting the sieve group of $a$ or $b$ by testing it against modulo $k$, I don't know which of the values $a$ or $b$ will be sieved out. So I can't merge it with different sieve groups.
How to determinate what value will be sieved out $a$ or $b$?