Share Your Experience: Take the 2024 Developer Survey

# Tag Info

### Is there an efficient algorithm to find whether an integer is a prime power?

See: Daniel J. Bernstein. Detecting perfect powers in essentially linear time, Mathematics of Computation 67 (1998), 1253–1283. Here, "linear" means "linear in $\log N$". ...
• 22.2k
Accepted

### Is there an efficient algorithm to find whether an integer is a prime power?

Note that if a number $N$ is a power of a prime $p$ it will be of the form: $$N=p^i \ ,$$ Since $p$ is prime, $p \geq 2$ which implies $i \leq \log_2 N$. We can compute the $i$th roots of $N$ for each ...
• 898
Accepted

### Complexity class of integer factorization

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 ...
• 277k
Accepted

### What is this algorithm computing and how to prove it?

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 ...
• 11.6k
Accepted

### How is integer factoring not in $P$?

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 ...
• 18.2k

### Is integer factorization reducible to subset sum?

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 ...
• 161k
Accepted

### Complexity of finding factors of a number

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 ...
• 81.8k
Accepted

### Is Determining the Number of distinct Prime Factors Polynomial?

No problem involving factorization is known to be polynomial time, and these problems (formulated as decision problems in any reasonable way) are suspected to be NP-intermediate. The only problem ...
• 277k

### Complexity of finding factors of a number

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)$ (...
• 277k
Accepted

### How does Pollard's rho algorithm work?

The idea behind Pollard $\rho$ is that if you take any function $f : [0, n - 1] \to [0, n - 1]$, the iteration $x_{k + 1} = f(x_k)$ must fall into a cycle eventually. Take now $f$ as a polynomial, and ...
• 14.1k

### What is the true space-complexity of saving all divisors, because $N$ can have more divisors than the length of $N$?

“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 ...
• 30.4k
Accepted

### Fast identification of prime power factors?

In the worst case, this is probably about as hard as factoring. As far as we know, factoring squarefree integers is about as hard as factoring integers in general, so for the case $e=1$, this is ...
• 161k
Accepted

### How to approximate big composite number factors?

Nope. The factoring problem is believed to be hard. Without knowing the full factorization, for any guess at the top digits of B you can reconstruct a set of top digits of C that would be consistent ...
• 161k

### Factoring algorithms after number field sieves

From the first line of Wikipedia's GNFS page: "the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than" The following ...
• 237

### Prime checking and factorization with just bit cheking

Given any specific candidate divisor $d$, it is easy to check whether $d$ is a divisor of the number (the standard modular reduction algorithm is a generalization of those tricks you mentioned). This ...
• 161k

### Decidability of factoring algebraic equations

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 ...
• 39k
Accepted

### Proof Review: Integer Factorization is in NP

You are missing something. If you are given what is supposed to be a factorisation of a number x, it's not enough to show that the product of those numbers is x. You also have to prove that all the ...
• 30.4k

### General number field sieve is slower then exhaustive search for 'small' numbers?

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 ...
• 277k

### Is the runtime for the general number sieve given in base 10, e or 2?

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 ...
• 277k
Accepted

### What is fastest algorithm for factoring out square from number

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 ...
• 277k

### integer factoring using Fermat's method

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 ...
• 30.4k
Accepted

### Period of modulo exponentiation function from factors

The quantity $r$ is known as the order of $a$ in the multiplicative group $\mathbb{Z}^*_N$. The order of the group is $\phi(N)$, which you can compute if you know the factorization of $N$. Next, you ...
• 277k
Accepted

### Is there an alternative to full factorization for testing the Polya conjecture?

You can use a sieve to significantly improve the running time. Decide on a number $N$, say $N = 2^{30}$. Initialize an array of length $N \times 2$ bits: one to keep track of the parity of the number ...
• 277k
Accepted

### What computational model supports arbitrarily sized integers?

I suspect you're looking for either the RAM model or the transdichotomous model. They differ primarily in how they take into account the size of integers and their effect on the time of various ...
• 161k
Accepted

### How would it be possible that primality testing is in P, but not factorization?

First of all, it doesn't make sense to talk about solving any particular formula in polynomial time--every specific formula can be solved in constant time (the answer is either yes or no, we just don'...
Accepted

• 2,053
1 vote

### How would it be possible that primality testing is in P, but not factorization?

"Primality testing can be reduced to the satisfiability of a multiplication circuit" - that's right, or close enough, because it can be reduced to the non-satisfiabilty of a multiplication ...
• 30.4k

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