Found a method for factoring numbers

Question

Let $N$ be the number that we want to factor such that $N=xy$ where $x,y$ are primes and $0<x<y$

By experiment, I found a function that can factor such numbers, please help me prove that it indeed can factor any such number and may be other numbers as well.

So here we go: By experiment, I found that in 80% of the time, there is an integer $i$ such that $\gcd(f(i),n)$ equals to $x$ or $y$

$$f(i)=i^{p-1}-1\ \text{ mod }N$$

• $p$ is a prime number such that $p > x$
• $0<i<x-1$

Note that we don't need to know $x$ in order to satisfy $p>x$. Since $x<y$ implies $x<\sqrt{N}<y$, so we can pick $p>\sqrt{N}$

Also, I found that if $\gcd(f(i),N)$ equals to $x$ or $y$ then for every $k$ such that $i<k<x-1$. $\gcd(t(k),N)=\gcd(f(i),N)$

$$t(k)=f(i)\cdot f(i+1)\cdot f(i+2)...f(i+k)$$

So if we take random values of $k$ near by $\lfloor\sqrt{N}\rfloor$ for each value of $gcd(t(k),N)$ we calculate we will have 80% to factor $N$

Note that $(x-1)^{p-1}-1\mod{n}$ is always divisible by $x$ as prooven here.

Here are few examples of my tests:

$x=1462691, y=415577, N=607860737707$
$p=779749$

$gcd(28^{p-1}-1\mod N,N)=y$

---

$x= 847213, y=209449, N=177447915637$
$p=421273$

$gcd(167^{p-1}-1\mod N,N)=y$

I wrote a small Java code that demonstrates this algorithm, I been able to solve integers up to the size of $2^{60}$. Quadratic-Sieve, for example, can solve integers of the size $2^{230}$ in the same time.

The biggest problem with this idea is that I don't know how to calculate $t(k)$ efficiently(here is a related question about it), I do it recursively at the moment.

Please help me prove that this is indeed a factoring method!

Java code:

BigInteger root = SqrRoot.bigIntSqRootCeil(n);
for (int j = 0; ; j++) {
    BigInteger a = ONE;
    for (int i = 2; i < 100; i++) {
        BigInteger bigI = BigInteger.valueOf(i);
        BigInteger result = bigI.modPow(bigPrime.subtract(one), n).subtract(ONE);
        a = a.multiply(result).mod(n);
    }
    BigInteger gcd = a.gcd(n);
    if (gcd.compareTo(ONE) > 0 && gcd.compareTo(n) < 0) {
        System.out.println(gcd + " with " + bigPrime);
        return;
    }
    bigPrime = root.add(BigInteger.valueOf(j));
}

Answer 1

The method by which your approach factors $N$ is by solving the problem:

• Find a $(p-1)$-th root of unity modulo $x$ (or modulo $y$).

If $i$ is such a thing modulo $x$ but not modulo $y$, then you have $\gcd(f(i), N) = x$.

The method by which you solve this problem is:

• Pick a range of consecutive integers. Hope one of them is a solution.

Of course, $(p-1)$-th roots of unity tend to be rare. In the worst case, if $\gcd(p-1, x-1) = 2$, then you will only succeed if you happened to pick a number that is $\pm 1 \bmod x$ (but not modulo $y$).

In your analysis, you recognize this; by picking $k \approx \sqrt{N}$ and testing $k$ consecutive numbers, basically what you are doing is guaranteeing that your interval contains every residue class modulo $x$, and consequently it must include all of the $(p-1)$-th roots of unity.

Once we recognize what your algorithm is doing, it's clear that it's quite wasteful; with much less work you could just compute

$$ t(k) = i \cdot (i+1) \cdot \ldots \cdot (i+k) \pmod N $$

and try to factor by computing $\gcd(t(k), N)$.

Alternatively, we could try to better exploit the idea of finding $(p-1)$-th roots of unity. It's clear that picking $p$ prime is the wrong thing to do; what you want is for $p-1$ to have a large common factor with $x-1$, and you have a better chance of that by making $p-1$ a product of lots of small numbers.

Then, rather than exhaustively searching for a root of unity (or randomly), we could instead try to construct one. This basically leads to Pollard's p-1 algorithm.