Skip to main content
Share Your Experience: Take the 2024 Developer Survey
17 votes

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 $". ...
Pseudonym's user avatar
  • 22.2k
10 votes
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 ...
SilvioM's user avatar
  • 898
9 votes
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 ...
Yuval Filmus's user avatar
7 votes
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 ...
nir shahar's user avatar
  • 11.6k
7 votes
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 ...
Luke Mathieson's user avatar
6 votes

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 ...
D.W.'s user avatar
  • 161k
6 votes
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 ...
David Richerby's user avatar
6 votes
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 ...
Yuval Filmus's user avatar
5 votes

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)$ (...
Yuval Filmus's user avatar
5 votes
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 ...
vonbrand's user avatar
  • 14.1k
4 votes

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 ...
gnasher729's user avatar
  • 30.4k
4 votes
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 ...
D.W.'s user avatar
  • 161k
3 votes
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 ...
D.W.'s user avatar
  • 161k
3 votes

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 ...
Nike Dattani's user avatar
3 votes

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 ...
D.W.'s user avatar
  • 161k
3 votes

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 ...
John L.'s user avatar
  • 39k
3 votes
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 ...
gnasher729's user avatar
  • 30.4k
3 votes

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 ...
Yuval Filmus's user avatar
3 votes

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 ...
Yuval Filmus's user avatar
3 votes
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 ...
Yuval Filmus's user avatar
3 votes

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 ...
gnasher729's user avatar
  • 30.4k
3 votes
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 ...
Yuval Filmus's user avatar
2 votes
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 ...
Yuval Filmus's user avatar
2 votes
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 ...
D.W.'s user avatar
  • 161k
2 votes
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'...
Zachary Vance's user avatar
2 votes
Accepted

Time complexity of a problem in probabilistic inference on a Bayesian network

Your problem is equivalent to: Given: real numbers $a_1,\dots,a_n \in \mathbb{R}$; a real number $t \in \mathbb{R}$ Goal: count the number of binary vectors $(x_1,\dots,x_n) \in \{0,1\}^n$ such that $...
D.W.'s user avatar
  • 161k
2 votes
Accepted

Is there a hypothesized "complete" class of problems between P and NP-hard?

One could reasonably defend a Yes or No answer. Yes: consider, e.g., the class of GI-complete problems. Similarly, for any NP-intermediate problem Q, you can define the class of problems that can be ...
D.W.'s user avatar
  • 161k
2 votes

Is GNFS quasi-polynomial-time?

Using the same variable $n$ to mean two different things in two places is confusing. In the context of your question, I think it is better to describe the running time of GNFS as $$\exp\left( (c+o(1))...
D.W.'s user avatar
  • 161k
1 vote

Integer/prime factorization to 3 SAT

I understand that a Satisfiable instance at most will let me know that this number is prime It's the other way around: if the instance is satisfiable, then the number of interest (let's call it $Q$) ...
user555045's user avatar
  • 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 ...
gnasher729's user avatar
  • 30.4k

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