# Tag Info

30

Since your algorithm is "fast", why did you only try it with a 15-digit number and not with a 232-digit one? There's serious money to be made if you indeed have a "fast" algorithm. Your algorithm takes time (if we count "div" as taking constant time) proportional to $\sqrt{n}$. A $d$-digit number can be as large as $10^d$, so your algorithm takes time ...

26

You are confusing the number $n$ with the number of bits needed to represent $n$. Here $b =$ the number of bits needed to represent $n$ (so $b \approx \lg n$). This makes a huge difference. A $O(n)$-time algorithm is a $O(2^b)$-time algorithm -- exponential in the number of bits. In comparison, the "efficient" algorithm you found has a running time that ...

24

The best estimate I know of can be found in Efficient networks for quantum factoring, by David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill, which gives $72 (\log N)^3$. Having said that, a straight comparison of number of steps on a quantum computer versus number of steps on a classical computer is problematic for various ...

12

The point is that the complexity of an algorithms is measured in the size of the input. For a number $n$ its size, the length of its representation, is $\log n$ bits.

12

A certificate for there being no non-trivial divisor of $m$ smaller than $r$ is the factorization of $m$. We can check in polynomial time that all factors are indeed prime (since primality is in P by AKS primality test), that their product is $m$, and that all of them are at least $r$.

7

Factoring is not known to be even in $\mathsf{P}$. Primality is not known to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).

7

The algorithm computes the greatest common divisor, or gcd for short. You are correct that the output is the product of common factors, since the gcd is known to be equivalent to it. In fact, this algorithm is known as Euclid's algorithm.

6

To add to Yuval's answer: AKS primality testing was discovered in 2002. Prior to that we didn't have a polynomial time algorithm to check if a number is prime. However Pratt discovered in 1975 what is now known as Pratt certificates for primality and proved that Primes is in NP. We can include these Pratt certificates of primality for the factors in our ...

6

I don't understand how the reduction from FACT to 3-SAT works. Are there any simple articles in which I can read about it? Most of the reading material assumes several steps of knowledge. First, you should read about how logic circuits (logic gates) work. Optionally learn or use a simple multiplication algorithm. You might want to start with the long-...

6

Integer factorization (or rather, an appropriate decision version) is not known to be NP-complete. In fact, it is conjectured not to be NP-complete. However, any reasonable decision version of integer factorization is in NP, and so reducible to any NP-complete problem (by definition). There are specialized algorithms for integer factorization which are ...

6

One of the things to remember when dealing with natural numbers (and others, but naturals are the central things here) is the encoding, and that the definitions of $P$ and $NP$ reference the length of the encoding of the input on a Turing Machine (or something closely equivalent). So the input to integer factoring, as a decision problem, is typically two ...

6

Yes, such a reduction exists. Subset Sum is NP-complete. FACT is in NP. Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum. To find such a reduction explicitly, work through the proof of NP-completeness for Subset Sum; it will describe such a reduction. (Implicitly, we get a reduction from FACT to SAT by Cook's ...

5

The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size $O(\log n)$ (where $n$ is the input size, which in your case is the logarithm of the number you want to factor). This means that in a constant amount of time the first model ...

4

Square roots can be computed via several methods (binary search, Newton iterations) rather fast. Note, however, that you are computing floating-point square roots, which are implemented by hardware and so should be even faster; but they are less appropriate if you want to factor large numbers, since floating-point computations are only approximate, and ...

4

What you are asking for does not exist, for good reasons. Today there is no existing computer that can execute Shor's algorithm. To run Shor's algorithm, you need a quantum computer, which doesn't exist yet. Therefore, you shouldn't expect precise estimates of its speed or running time, as that will depend upon the details of the computer that the ...

4

As far as I know, there are no non-trivial lower bounds on factoring, and in particular, no variant is conjectured to be NP-hard. (While factoring is not a decision problem per se, you can make up a corresponding decision problem that gives the $k$bit of the $\ell$th smallest factor.) As far as algorithms go, there are a great many of them, including the ...

4

Large numbers are factored with the General Number Field Sieve, which is, as of now, the fastest non-quantum algorithm. You can find the heuristic runtime in the linked Wikipedia-article. Also in use is the Elliptic Curve Factorization, which needs longer runtime in the worst-case, but has the advantage that the runtime depends on the second-largest factor. ...

4

The language of tuples $\langle n,i,j,b \rangle$ such that the $j$th bit of the $i$th prime factor of $n$ is $b$ is in NP. In particular, it is in #P. More accurately, there is a #P algorithm that on input $\langle n,i,j \rangle$ gives the $j$th bit of the $i$th prime factor of $n$ (either $0$ or $1$). Since the permanent is #P-complete, we can reduce this ...

4

When you assume that arithmetic operations can be done in time $O(1)$, you're assuming that the numbers you're dealing with have a constant maximum number of digits. That's not a reasonable assumption when you're dealing with factorization: for any number $d$ of digits, there are a fixed, finite number of integers with at most $d$-digits and you can ...

4

“Saving all divisors” is just not a clever way to go about it. It’s much better to factor N into the product of powers of distinct primes, which has about the same size as N, and all divisors can be enumerated from that easily. But then, if N has n bits, it can be the product of about n/log n primes of log n bits each, so there are about 2^(n / log n) ...

3

The most efficient method is to use a sieve; this is why the method is called the quadratic sieve. It should be mentioned, though, that the sieve is just an optimization over Dixon's method, and doesn't affect the asymptotic running time apart from some (multiplicative) lower order terms. For a description of the sieve, you can start with Wikipedia.

3

The computational complexity of factorization is one of the biggest open problems in computer science. There's a summary of what's known on Wikipedia; the summary of the summary is that it's known to be in both NP and co-NP so it's unlikely to be NP-complete, or the polynomial hierarchy collapses.

3

there are several ways to conceptualize this, esp using the psychological concept of chunking which is rougly equivalent to the use of "abstraction(s)" in CS. what part is hard to understand? the conversion of factoring to SAT is much easier to understand if you learn how EE circuits implement binary arithmetic (mainly addition), and to note that ...

3

There is currently no known (asymptotical) more intelligent algorithm (and it is also not expected that there should be one) than if factorizations of $m$ and $n$ were not known (assuming $m$ and $n$ to be coprime). Even the case where $2$ is a prime factor doesn't count, because checking some of the smallest prime numbers can be done without much effort ...

3

You absolutely don't have to compute most of the square roots. You want to know whether the square root of $x^2 - n$ is an integer, that is you want to know whether $x^2 - n$ itself is a square. You don't need to know the actual square root as long as you know it is no integer. Take d = 20,160 and create a bitmap of which integers are a square modulo 20,...

3

First of all, you're misstating integer factorization: your version is completely equivalent to primality. Second, there were primality certificates which could stand for a polytime primality testing algorithm. These are polytime verifiable certificates of primality.

3

Using state of the art factoring algorithms, you can substantially improve on the algorithm you state. It appears that no algorithm better than factoring is known at the moment. See this question on mathoverflow.

3

Wikipedia gives the running time as $$\approx \exp \sqrt[3]{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3},$$ where $n$ is the integer being factored. Here $\ln n$ is the natural logarithm (logarithm to base $e$).

3

First of all, the number 120 that you got is completely meaningless. There is a scaling factor that can only be determined experimentally. Even worse, there are lower order factors which are probably very significant for such small numbers. Finally, the running time you quote is heuristic – it's just an educated guess. You are correct that GNFS is a lot ...

3

Interesting question. Factorization of functions, including factorization of polynomials is in fact a classical problem throughout history of mathematics. For the sake of contradiction, assume that $$x^2 + y^3 - e^{z} = f(x)*g(y)*h(y,z)$$ For the sake of simplicity, assume that $f, g, h$ are continuously differentiable inside $D$, the place where we are ...

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