# Tag Info

### 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 ...
• 24.8k

### 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 ...
• 201
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 ...
• 6,986
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 ...
• 37.4k
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 ...
• 12.2k
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)$: ...
• 4,513

### 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 ...

### 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 ...
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]...
• 196
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 ...
• 12.2k

### pq factorization

Hart's one-line factorization algorithm can do it in 150 microseconds with my unoptimized implementation (in PARI/GP): ...
• 1,745
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 ...
• 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: ...
• 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 ...
• 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://...
• 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 ...

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