Skip to main content
13 votes

Is the 2016 implementation of Shor's algorithm really scalable?

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 ...
Peter Shor 's user avatar
10 votes

What is worst case complexity of number field sieve?

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 ...
djao's user avatar
  • 201
9 votes
Accepted

Factoring assuming smoothness of some numbers

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 ...
Jeffrey Shallit's user avatar
6 votes
Accepted

What's the complexity of factoring over a set of generators (say in $GL_2$)?

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 ...
Joshua Grochow's user avatar
5 votes
Accepted

Does being able to efficiently factor semiprimes allow to efficiently factor any integer?

That statement is not known to be true -- and I note that since you posted your question, it has been edited. We do not know of any proof that if you can factor products of two primes, you can factor ...
D.W.'s user avatar
  • 12.2k
4 votes
Accepted

How does gcd in $\mathbb Z_p[x]$ and $\mathbb Z_q[x]$ relate to gcd in $\mathbb Z_n[x]$?

To explain their proposition, let me recall Euclid's algorithm to compute the gcd of $b(x)$ and $c(x)$: ...
Bruno's user avatar
  • 4,513
4 votes

The factoring problem reduces to order finding or is it the other way around?

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 ...
Frédéric Grosshans's user avatar
3 votes

Continued Fraction Algorithm in Shor's Algorithm

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 ...
Conn-CaoYK's user avatar
3 votes
Accepted

Comparing Shor's and Regev's Quantum Factoring algorithm

First some background (that does not fit the comments section) since you asked for pointers: The continued fractions-based post-processing algorithm in Shor's order-finding algorithm [Shor94] [Shor97]...
Martin Ekerå's user avatar
3 votes
Accepted

Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?

In a practical sense, Levin search is not useful. It has an enormous constant factor (exponential in the length/size of the optimal factoring algorithm). This makes it of little use in practice. In ...
D.W.'s user avatar
  • 12.2k
2 votes

pq factorization

Hart's one-line factorization algorithm can do it in 150 microseconds with my unoptimized implementation (in PARI/GP): ...
Charles's user avatar
  • 1,745
2 votes
Accepted

Would the following be an acceptable part of an algorithm if used for prime factorization

It's not cheating. The last step of an algorithm can certainly be: compute $n/p_1$ and check whether that is an integer and is prime. That's an allowable step in an algorithm and can be computed ...
D.W.'s user avatar
  • 12.2k
1 vote

factoring large numbers

(This would be more suited as a comment, but I don't have enough reputation to post one) As someone already posted in the comments: ...
ynwarcs's user avatar
  • 111
1 vote
Accepted

Is it possible to prove that a general purpose integer factorization algorithm must contain a loop?

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 ...
D.W.'s user avatar
  • 12.2k
1 vote

Fast Reduction from RSA to SAT

you can (batch) generate very efficient DIMACS files of any bit-size with Paul Purdom and Amr Sabry's CNF Generator locally now with this GitHub repo which is also available on IPFS ipfs://...
alephc's user avatar
  • 11
1 vote

An NP-complete variant of factoring.

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 ...
Mohammad Al-Turkistany's user avatar

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