An algorithm to reduce a factorisation problem into an easier one?

Question

Question

I recently wondered about my own factorisation method (see method) to generate a smaller number to factorise than the original one.

What are some "good methods" to choose $\lambda$ and $\beta$? What will be the computational time of this algorithm? Is it better than just dividing the number with all the primes less than the square root of the number? Does it always give a smaller number to factorise than we began with?

Method

It works as follows:

Consider the an arbitrary number $c$ to be factorised into it's prime factors $a<b$:

$$c = ab$$

Let us define $k = \lfloor \sqrt{ c } \rfloor $ using the floor function.

$$N + c^\lambda = \beta \prod_{i=2}^{p_n<k} p_i $$

where $\beta$ is an arbitrary number that consists of the primes ($3$ to $p_{n}\leq k$)raised to an arbitrary power including $0$. Hence, $\beta \geq 1$

Subtracting $2 c^\lambda$ on both sides :

$$ N -c^\lambda= \prod_{i=2}^{p_n<k} p_i . \beta - c^\lambda = a\kappa $$

Taking modulus both sides:

$$ |N -c^\lambda|= a|\kappa| $$

Let us factorise $N -c^\lambda = a\kappa$ where $\kappa$ is the number one gets out of the arithmetic and $a$ is taken common. We choose $\lambda$ and $\beta$ such that we minimise $|N -c^\lambda|$.

Hence, by factorising $ |N -c^\lambda|$ we will find $a$.

Answer 1

Let me see if I can make some sort of sense of this:

we are looking for a prime divisor $a$ of a composite number $c$

1. Calculate $$q := \prod_{p^2 < c} p$$ the product of all primes $< \sqrt c$. Since $c$ is composite, it must have a prime divisor in common with $q$.
2. Search for $\beta, \lambda$ that minimize the expression $$N = \beta q - c^{\lambda}$$ (Your arithmetic is wrong where you "subtract $2c^\lambda$ on both sides".) Any common divisor of $c$ and $q$ will also divide $N'$.
3. Find a prime factor $a$ of $N$ less than $\sqrt c$. Since $c^\lambda = \beta q - N$, $a$ must be a prime divisor of $c^\lambda$ and therefore of $c$ itself.

Is this correct?

This will work, but unless you have some magical trick for calculating $q$ other than knowing all the primes $\le \sqrt c$, it will be much harder than simply dividing $c$ by each of those primes and seeing which leaves no remainder. It is about as easy to divide $c$ by a prime $p$ as it is to multiply $p$ by another number (i.e., the product of the smaller primes).

Even if you do have some magical trick for calculating $q$ without knowing the primes, it would be easier once you know $q$ to use the Euclidean algorithm to find the gcd of $c$ and $q$, as opposed to searching for $\beta, \lambda$ that minimize $N$.