# Integer factorization with sieving

I am trying to solve the Integer Factorization problem using the sieving method, and I was wonder if there been a study in this area and if there more on this topic that I can read? Note, I am not interested in more successful methods of factoring, like quadratic sieve or the general approach.

The main idea behind sieving is to separate possible solutions from impossible solutions.
If $N$ is the number we want to factor, we can look in to Fermat's equation: $$a^2 - N = b^2$$

Than pick up a small prime number $k$, and try to find all the possible options for $a$ such that:

$$(a^2\mod k) - (N\mod k) = b^2\mod k$$

Than we can search for factors of $N$ by examine all those options over cycles of $k$

• until integer solution for Fermat's equation been found do the fallowing
1. test all the options of $a$ that you found, with the addition of $k$ multiply $i$, $i$ is an integer value starting at 0
2. increase $i$ by 1

This method become more effective as the ratio between the cycle to the group of numbers to be tested increases. Also there is an option to merge tow different cycles.

Let it be $k_1$ the cycle length and $g_1$ the group of the numbers that been tested over the this cycle. And we want to merger it with $k_2$, $g_2$ a different group from the same $N$.

The new cycle length will be the multiplication of $k_1$ and $k_2$ and the group values will be all the shared values of $g_1$ and $g_2$ over $k_1k_2$ cycle.

The merge improves the ration between the number of values in the group and the cycle length. In the wiki article, they explain a private case of this idea when they are merging it with $k=2$ and a random $k$ value.

From my tests I been able to get to the ratios in a range of $2^9$ and $2^{13}$, obviously the goal is to get a ratio of $2^{500}$, it will allow to break RSA.

I have another several ideas that I am working on, but no results just yet.

• Find all the solutions for $$(x\mod k)(y\mod k)=N\mod k$$
1. if $N\mod k$ is not quadratic value then the group of $x$ options and $y$ options must not have shared values, otherwise those values could be sieved out.
• Find all the solutions for $$((a\mod k)-(b\mod k))((a\mod k)+(b\mod k))=N\mod k$$ and combine it with $(x\mod k)(y\mod k)=N\mod k$
• In $(a^2\mod k) - (N\mod k) = b^2\mod k$ $a$ and $b$ will have the same modes if $k$ is a factor, otherwise you can sieve the same values out.

So I really like to investigate this idea father and I want to know if some body already did.

## 2 Answers

Look up Lehmer sieve.

Here are some of the references a search found:

http://ed-thelen.org/comp-hist/Lehmer-NS-01.html

http://ed-thelen.org/comp-hist/Lehmer-NS03.html

http://en.wikipedia.org/wiki/Lehmer_sieve

http://computer.org/cms/Computer.org/computer-pioneers/pdfs/L/Lehmer.pdf

• Thanks the reference, but aren't those a private case to what I described? They did not performed a merge. – Ilya Gazman Mar 1 '15 at 22:36

I would say jump out of the modular world and look at the Diophantine equation $$B(t^2-s^2) +(a+b)t+(a-b)s+m =z$$ where $a$ and $b$ are co-prime to $B$, $z = (N-r)/B$, $$r \equiv ab\: \mod B.$$
Now you can search for $t$ and $s$ in a easily understood search area in one of the multiplicity of spaces defined by ab congruent to $r \mod B$. The fastest sequence to run this algorithm over generally is the primorials.