1
$\begingroup$

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));
}
$\endgroup$
12
  • $\begingroup$ On the two bullet points regarding the definition of $f(i)$ 1. "$p$ is a prime number such that $p>x$" 2. "$0<i<(x−1)$" How can you refer to $x$ at this point in your argument you do not know what it is yet? Also sometimes you refer to N and other times n. $\endgroup$ Nov 22, 2017 at 0:53
  • $\begingroup$ @JamesArathoon I updated $N$. Note that $x<\sqrt{N}<y$ $\endgroup$ Nov 22, 2017 at 1:08
  • $\begingroup$ Ok that still leaves how you determine that $i<(x-1)$ $\endgroup$ Nov 22, 2017 at 1:16
  • $\begingroup$ @JamesArathoon just take values for $i$ that are close to 0 $\endgroup$ Nov 22, 2017 at 1:33
  • $\begingroup$ If $P_{prod}$ is the product of all the primes between 3 and floor($\sqrt{N})$, given $x<\sqrt{N}<y$, then $gcd(P_{prod},N)=y$. You presumably are seeking a way of calculating $P_{prod}$ without having to do $\pi(floor(\sqrt{N}))$ multiplications; where $\pi(n)$ is the number of primes less than or equal to n. $\endgroup$ Nov 22, 2017 at 1:45

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Wow man, this is awesome! I am going to read more about Pollard ;) $\endgroup$ Nov 22, 2017 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.