139

I have to admit (surprising as it sounds) that I don't know really the answer. I either discovered or rediscovered this reduction myself. I discovered the discrete log algorithm first, and the factoring algorithm second, so I knew from discrete log that periodicity was useful. I knew that factoring was equivalent to finding two unequal numbers with equal ...


55

The random reduction from factorization to order-finding (mod N) was very well known to people working in number theory algorithms in the late 1970's and early 1980's. Indeed, it appears in a paper of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179, and Eric Bach and I knew it before then. I am ...


16

This isn't my answer, but Terrence Tao gave a beautiful answer to this question on MathOverflow. Here are the first few lines of his answer. To read the complete answer, follow the link. There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n ...


14

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. ...


13

One approach on this question, related to complexity-theoretic questions, is due to Shub and Smale [1] who proved that if $n!$ is ultimately hard to compute, then $\mathsf{VP}\neq\mathsf{VNP}$ over some field. Their model of computation is the straight-line programs: The goal is to compute $n!$ from the constant $1$, using only additions, subtractions and ...


11

The problem stems from the fact that your understanding of quantum computing (as outlined in the question) is incorrect. Certainly quantum computers are poorly explained in most popularizations. A quantum computer cannot simply check if a solution exists within a superposition deterministically, let alone in unit time. The most general representation of the ...


11

We can show that if all $\alpha_i$ are different, then square removal and factoring of $n$ are equally hard. It is obvious, that if we can factor $n$, we can also compute square removal of $n$. The other direction is a bit more tricky. First compute the square removal of $n$ and let's call this $m$. From the definition it follows that $m$ divides $n$. ...


11

The main thrust of Cao and Luo's argument is that in the variant of the algorithm that was implemented, the first register—that eventually contains the output—contains only 1 bit. And if you only get 1 bit of output from the algorithm, that's insufficient for factorization. (For one thing, although this isn't their argument, 1 bit clearly does not contain ...


10

I believe no polynomial algorithm is known. According to a paper this is used in at least one cryptosystem: Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method. ...


9

I'm not sure this is a statement about primes so much as it is a statement about secret key generation: if the method is deterministic (e.g. take the smallest prime larger than 10^20), then your adversary can simply reproduce the computation to find your secret key.


9

No, the intuitive observation "There are about $\sqrt{n}$ prime factors to try" does not imply a lower bound on the complexity of factoring. There is absolutely no reason that a factoring algorithm must try every possible prime factor, or even that the algorithm's behavior should resemble "trying" different factors at all. Even though precisely the same ...


9

Elaborating on Joe's earlier answer: note that $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$. The latter is the second lowest class in the "low" hierarchy: which is to say that $\mathsf{NP^{NP \cap coNP} = NP}$. This implies in particular that $$\mathsf{P^{\textrm{FACTORING}} \subseteq NP^{\textrm{FACTORING}}} \subseteq \mathsf{NP}.$$ We may make similar ...


9

See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time polynomial in $\log N$ and $k$ and $B$. In particular this gives a $(p+1)$-method (see the earlier work of Williams) and $(p^2+1)$ method. http://www.ams.org/...


8

Most of the state of the art factorization methods, e.g. Quadratic Sieve, Number Field Sieve, Elliptic Curve Factorization use variants of the ideas you suggest. The Elliptic curve method is completely probabilistic in that you pick a curve and a point raise the point to a power and check to see if you have found a factor (this is vastly oversimplified, but ...


8

I’ll comment on why a relation as in the question $$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$ (for every $n$) helps factoring. I can’t quite finish the argument, but maybe someone can. The first observation is that a relation as above (and more generally, the existence of poly-size arithmetic circuits for $(2^n)!$) gives a poly-size circuit for computing $...


8

The textbook of Computational Complexity: Modern Approach, by Arora and Barak gives such example: They define the decision problem Integer Factoring on input of three positive integers, $\text{Integer Factoring} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$. They state that Alon and Kilian showed that if ...


8

Let $\mathbb K$ be a field of characteristic $0$ or at least $d(d-1)+1$, and $p\in\mathbb K[x_1,\dotsc,x_n]$ be a polynomial of total degree at most $d$. If $d$ is fixed and $n$ is growing, one has the following complexity bounds for the reduction of the factorization of $p$ to the factorization of a degree-$d$ univariate polynomial: (The notation $\tilde{\...


7

Yes, assuming you want both $f_1(x)$ and $f_2(x)$ with integer coefficients. One of the reasons why LLL is so popular is precisely because it gives a polynomial time algorithm to factor polynomials with integer coefficients. For an excellent introduction, I recommend C. Yap's "Fundamental Problems in Algorithmic Algebra" (available online, for free), ...


6

All of the following algorithms either find a complete factor or a complete non-trivial factorization: Trial division. Pollard rho. Pollard $p-1$ and its variants, including the elliptic curve method (ECM). Shanks' SQUFOF. Quadratic sieve (QS). Number field sieve (NFS). As far as I understand this list includes all algorithms actually used to factor ...


6

In the past few months, a version of the number field sieve has been analyzed rigorously: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring Basically the worst-case running time is $L_n(1/3, 2.77)$ unconditionally and $L_n(1/3, (64/9)^{1/3})$ under GRH. This is not for the "classic" number field sieve, but a ...


6

(This is shameless self-promotion.) If you don’t mind either assuming the generalized Riemann hypothesis (for $L$-functions of quadratic Dirichlet characters) or using randomized polynomial time, then the following search problems work: Given integers $n,a$ such that the Jacobi symbol $\left(\frac an\right)=1$, output either a square root of $a$ modulo $n$, ...


6

This is usually called the (constructive) membership problem (rather than a "factorization" problem). The membership problem is to decide whether $C \in \langle A,B \rangle$; the constructive membership problem is to actually find a word (if any) in $A,B$ that equals $C$. Its complexity may depend on whether you want to allow $A^{-1}, B^{-1}$ in your word (...


5

There are ways to see that either the answer is probably no, or that the question means more than one thing and has a negotiable answer. On the one hand, the PCP theorem says that many, but not all, NP-hard problems are still NP-hard to approximate. The standard belief is that Grover's search algorithm, which gives you a quadratic speedup but no more ...


5

Yes, that's exactly the idea. It is inspired by the following fact: Theorem. Let $\psi$ be an irrational number, and suppose $|\psi - s/r| \le 1/2r^2$. Then $s/r$ is one of the convergents of the continued fraction expansion of $\psi$. In other words, every "very good" approximation to $\psi$ can be obtained by computing the continued fraction ...


3

If $0 \le k_p < 2^{b/2}$ and $0 \le k_q < 2^{b/2}$, it's easy to factor such numbers. Consider: $$N = pq = (2^b-k_p)(2^b-k_q) = 2^{2b} -(k_p+k_q) 2^b + k_p k_q.$$ Under the stated conditions, you can read off the values of $k_p k_q$ and $k_p+k_q$ from the binary representation of $N$, since $0 \le k_p k_q < 2^b$ and $0 \le k_p+k_q < 2^b$. In ...


3

Unfortunately, the increase in density of targets isn't as great as you think; as you note there are $B$ multiples of $A$ less than $n$ and $A$ multiples of $B$ less than $n$. This gives you $A+B$ 'targets' to hit in an interval of size $n$. Picking $B\gt A$ for clarity, this means there are less than $2B$ total targets to hit, giving a probability of $\...


3

A major consequence of Factoring being in $P$ is that multiplication (of two equal size integers) is not one-way function. This would be very surprising result since multiplication is widely believed to be the strongest candidate for one-way function. However, this may not change the picture of complexity classes.


2

Not quite a complete answer, but seems to be an improvement: The research papers cited above compare the problem of computing eth roots mod N, i.e. doing the private key operation in the RSA cryptosystem, to the problem of factoring, i.e. finding the private key, in both cases, using only the public key. In this case, the factoring problem is not the ...


Only top voted, non community-wiki answers of a minimum length are eligible