# Questions tagged [factoring]

The tag has no usage guidance.

51 questions
Filter by
Sorted by
Tagged with
1answer
132 views

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

1) Let $A$ be a (general purpose) algorithm that factors $n$. Suppose $A$ contains a loop (which is hard to imagine if not impossible that it does not.) If $A$ contains nested loops then these loops ...
0answers
55 views

### Bit complexity of factoring univariate polynomial over $\mathbb{Q}$ (rationals)

What is the bit complexity of finding all the irreducible factors $f_1, ..., f_r$ of a degree-$d$ polynomial $f(x) = \sum_{i=0}^d a_i\cdot x^i \in \mathbb{Q}[x]$ whose all coefficients are $B$-bit ...
0answers
44 views

### Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?

Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ is irreducible what is the best technique to factor such ...
0answers
111 views

### Factorizing semiprime $n=pq$ with $p \mid q-1$

Could we find a fast integer factorization algorithm for any large semiprime $n=pq$, if we know that $p \mid q-1$?
1answer
132 views

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

In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know ...
0answers
194 views

### Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?

Given a primitive polynomial (gcd of coefficients is $1$) in $\Bbb Z[x]$ we have a polynomial time factoring algorithm for this that runs in time polynomial in degree $d$ and number of bits in ...
1answer
1k views

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

In the 2016 Science paper "Realization of a scalable Shor algorithm" , the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of  and Table 5 ...
1answer
179 views

### The factoring problem reduces to order finding or is it the other way around? [closed]

initially i was not at all equipped in theoretical computer science and knew only basics of number of theory. I started working from scratch on the age old problem of primality testing which led me to ...
1answer
100 views

### Factoring assuming smoothness of some numbers

I have came across a lot of factorization methods and most of them seem to assume smoothness of some numbers. For example When $p-1$ is smooth When $|E(\mathbb{F}_p)|$ is smooth. (Elliptic curve ...
0answers
283 views

### Does Factoring have a Statistical Zero Knowledge Proof?

The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to ...
0answers
110 views

### An NP-complete variant of factoring and relation to factoring [closed]

After reading this post An NP-complete variant of factoring. I come up with a question. To summerize the post, we have the factoring problem (F) which ask for a number $p$ that is prime and divides ...
2answers
493 views

### Alternatives to Diffie Hellman

Assume that Discrete logarithms can be solved in linear time over any group (hence factorization is also trivial by a result of Eric Bach), is there any other candidate public key exchange problem ...
2answers
2k views

1answer
896 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 ...
1answer
205 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 ...
1answer
342 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 ...
0answers
428 views

1answer
378 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 ...
1answer
243 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 ...
2answers
404 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 ...
2answers
2k 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 n$, ...
2answers
962 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 would ...
3answers
759 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 ...
1answer
354 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 ...
2answers
284 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 ...
5answers
4k 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 variables ...
3answers
3k views

2answers
3k views

### What are the consequences of factoring being NP-complete?

Are there any references covering this?