Questions tagged [factoring]

The tag has no usage guidance.

51 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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$?
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 ...
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 ...
1k views

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

In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 ...
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 ...
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 ...
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 ...
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 ...
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 ...
2k views

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 ...
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 ...
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 ...
428 views

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 ...
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 ...
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 ...
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$, ...
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 ...
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 ...
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 ...
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 ...
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 ...