143

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

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 ...


12

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 ...


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$. ...


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

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/...


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

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), ...


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 ...


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{\...


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 ...


7

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

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 ...


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 (...


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 ...


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 ...


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 ...


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 ...


2

I don't think you have to do iterations over $r'$ for checking. In fact, performing iterations would lead to $O(L^4)$ complexity instead of $O(L^3)$ as claimed in the textbook. So how do we know which convergent of the continued fraction is the one we are looking for? The way is as follows. First, I'll post some facts in number theory here. Fact 1. Let $ \...


2

Both! You may want to read the answers to this related question, and the 1987 paper of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179 cited in Jeffrey Shallit’s answer. This paper looks at the reduction between many problems in number theory, including primality, factorization, order-finding, ...


2

The Wikipedia page on "Post-quantum cryptography" provides a list of proposals for PKE resistant to quantum attacks. Quantum algorithms can solve DL in finite abelian groups (as well as a few nonabelian and infinite abelian ones), so they get very close to the spirit of the question you are asking. The learning with errors problem mentioned by one of the ...


1

It depends on the precise model of computation you work within. However, this doesn't seem to be a useful direction for proving lower bounds on the time to factor. Uniform algorithms Let's look at uniform algorithms. Suppose our model of computation is a Turing machine or the transdichotomous model or something similar, where each step can do at most a ...


1

Check Supersingular Isogeny Key Exchnage for some nice work on a Diffie-Hellman like Key Exchange based on isogenies between supersingular elliptic curves. This will compute computationally secure key. The authors mention that even though the key exchange is secure it will most likely be interesting purely for research/ pedagogical reasons. There also is a ...


1

I will assume that when you say that a natural number n is "very small," that you mean that for some constant j, n < j. Given n and a promise that its prime factors p,q, are both within j of 2^b for some natural number b and some natural constant j, it's not hard to construct a brute-force algorithm that checks every possible value of p and q in time ...


1

This is an informal efficient deterministic reduction idea (and may be incomplete): Fractran is a Turing-complete programming language. A suitably defined bounded-version of Fractran programs should be reducible to the language $ \{\langle L, U, M \rangle \;|\; (\exists \text{ a positive integer } p \in \{L, \ldots, U\})[p | M]\}$ For instance, a bounded-...


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