The tag has no usage guidance.

learn more… | top users | synonyms

-2
votes
1answer
98 views

A curious statement in an old blog

In http://blog.computationalcomplexity.org/2009/08/finding-primes.html, a statement is added which reads "Oddly enough we would usually prefer a probabilistic over the deterministic method to find ...
-3
votes
1answer
147 views

Consequences of polynomial time algorithm to variant of integer factorization

Given $N,U,V\in\Bbb N$ is there $n\in[U,V]\cap\Bbb N$ such that $n|N$ is $\mathsf{NP}$-complete modulo Cramer's conjecture on prime gaps is shown in An NP-complete variant of factoring. So supposing ...
1
vote
0answers
52 views

Efficient algorithm to find number of factors

Given an integer n, is there an efficient algorithm to find the number of factors of n?
2
votes
2answers
90 views

Factoring semiprimes whose factors very close to a power of two

Are there any factorization algorithms that run well on numbers $N = pq$ where $p,q$ are prime and $p = 2^b - k_p, q = 2^b - k_q$ for very small $k_p,k_q$? What about $p = 2^b + k_p, q = 2^b + k_q$ ...
16
votes
1answer
301 views

Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$

In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his ...
2
votes
1answer
122 views

Randomness versus Quantumness in factorization

The best deterministic factorization algorithm that is currently known runs in $O(N^{\frac{1}4+\epsilon})$ arithmetic steps. Randomness and quantumness improves upon this. I believe Quadratic/Number ...
3
votes
1answer
71 views

Algorithms for factorization using the decision version

Are there any practical algorithms for integer factorization that work by solving the decision version of the problem $\log N$ times to isolate a factor? Or is the decision version of only theoretical ...
1
vote
1answer
104 views

Continued Fraction Algorithm in Shor's Algorithm

I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$. We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies ...
8
votes
2answers
705 views

Is square removal easier than factoring?

It seems to me that the square removal task can be reduced to the factoring task, but that there is no way to reduce factoring to square removal. Is there a way to make this "feeling" more precise, ...
2
votes
1answer
264 views

Complexity lower bound of finding the factorial of a number

I was wondering about the complexity of the factorial of a number mostly because this problem is not referenced in the complexity books I have read. Two similar problems, Matrix Multiplication and ...
53
votes
2answers
5k views

Was the reduction in Shor's algorithm originally discovered by Shor?

This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was ...
8
votes
1answer
217 views

Factoring low-degree polynomials

What is the fastest algorithm known for factoring polynomials with $n$ variables and total degree $\leq d$? Here, $n$ is growing and $d$ is fixed. Most work seem to consider the case when $d$ is ...
3
votes
1answer
495 views

What NP-complete problems are most similar to integer factoring?

The exact complexity of factoring integers (the decision problem) is a major open question in TCS (with important implications, especially in cryptography because of the RSA algorithm), and is widely ...
5
votes
1answer
184 views

Oracles which put integer factorization in P

I'm compiling a list of as many problems (decision or function) as I can find such that, if I had an oracle that could solve the problem in P, then integer factorization would also be in P. Here is a ...
-2
votes
1answer
320 views

Computational complexities in factoring

[Note: n is a given integer (not the number of its digits)] I'd like to know how O(sqrt(n)/log(n)) would compare against the computational complexity of the best available algorithms (as well as the ...
14
votes
0answers
361 views

Semiprime factorization, Groebner bases and a Nullstellensatz certificate

Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ ...
0
votes
0answers
69 views

What is the best known hardness result for Factoring? [duplicate]

Possible Duplicate: Are the problems PRIMES, FACTORING known to be P-hard? In particular, do we know that $\mathrm{Factoring}$ is hard for $\mathsf{AC^0[p]}$, $\mathsf{ACC}$, or ...
15
votes
1answer
438 views

$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $?

While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post: If, for every $n$, there exists a relation of the form $$ (2^n)! = \sum_{k=0}^{m-1} ...
1
vote
0answers
164 views

Estimating the number of operations required to factorize a $b$-bit integer using GNFS

You may skip to question According to Wikipedia, the complexity of factorizing a number n using the general number field sieve is ("heuristically"): $ \exp\left( \left(\sqrt[3]{\frac{64}{9}} + ...
7
votes
1answer
337 views

Layman Interpretation: Quantum Factoring Algorithm

I must firstly express that I know only a little about quantum computing and my knowledge comes largely from popular science texts and the media. So, I'm hoping that somebody will be able to help me ...
4
votes
1answer
225 views

Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm?

Is it possible to design an efficient approximation algorithm for an $\sf{NP\text{-}complete}$ problem based on reductions from Shor's algorithm? Are known any (classical) approximation algorithms ...
2
votes
2answers
370 views

Factorization Using Statistical Methods

We consider a number $N=AB$ where $A$ and $B$ are primes. Along the whole number-line from $1$ to $N$ we have two success points or target points: $A$ and $B$. If we had millions of target points the ...
33
votes
2answers
1k views

Are the problems PRIMES, FACTORING known to be P-hard?

Let PRIMES (a.k.a. primality testing) be the problem: Given a natural number $n$, is $n$ a prime number? Let FACTORING be the problem: Given natural numbers $n$, $m$ with $1 \leq m \leq ...
28
votes
2answers
842 views

How hard is it to count the number of factors of an integer?

Given an integer $N$ of length $n$ bits, how hard is it to output the number of prime factors (or alternatively number of factors) of $N$? If we knew the prime factorization of $N$, then this ...
22
votes
3answers
692 views

Adding integers represented by their factorization is as hard as factoring? Reference request

I'm looking for a reference for the following result: Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation. (I'm pretty sure ...
11
votes
1answer
273 views

Lower bounds on the period in integer factorization?

In 1975, Miller has shown how to reduce the factorization of integer $N$ to finding the period $r$ of a function $f(x)=a^x\;\bmod\;N$ such that $f(x+r)=f(x)$ with some randomly chosen $a<N$. It is ...
0
votes
2answers
260 views

How to calculate the cost of factoring a large integer?

I would like to know how much it would cost to factor a large integer. The cost can be given computer operations, time to process it or even monetary value. I know there are people that factored 200 ...
23
votes
4answers
2k views

Fast Reduction from RSA to SAT

Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention: Build a public library of 3SAT instances, with as few ...
35
votes
3answers
2k views

Is the integer factorization problem harder than RSA factorization: $n = pq$?

This is a cross-post from math.stackexchange. Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that ...
12
votes
2answers
505 views

Reference for Levin's optimal factoring algorithm ?

In Manuel Blum's "Advice to a Beginning Graduate Student": LEONID LEVIN believes as I do that whatever the answer to the P=NP? problem, it won't be like anything you think it should be. And he has ...
25
votes
3answers
2k views

Consequences of Factoring being in P?

Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a ...
33
votes
2answers
2k views

An NP-complete variant of factoring.

Arora and Barak's book presents factoring as the following problem: $\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$ They add, further ...
13
votes
5answers
681 views

P with integer factorization oracle

I just read the "Is integer factorization an NP-complete problem?" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$: ...
12
votes
0answers
372 views

Reference request: a more complete “faster factorization into coprimes”

Some months ago, before the advent of "CS-Theory", I asked a question on MathOverflow about efficiently factoring an integer N into coprime factors n1 and n2, where n1 is a multiple of a given a ...
20
votes
2answers
948 views

Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
6
votes
1answer
545 views

Permanents - Approximation and connection to integer factorization

Given a non-negative integer matrix of size $n \times n$. If the permanent can be calculated in $n^{2}$ arithmetic operations but each operation is on word size $n^{k}$ bits for some constant $k$, ...
17
votes
2answers
2k views
-1
votes
1answer
6k views

Is integer factorization an NP-complete problem? [duplicate]

Possible Duplicate: What are the consequences of factoring being NP-complete? What notable reference works have covered this?