Multiplication Sieving

106 Views Asked by At

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$?