The factoring tag has no wiki summary.
-2
votes
0answers
43 views
Generating 3SAT circuit for Integer factorization example [closed]
I read somewhere that 3SAT can be used to solve Integer Factorization.
If that is true, could someone teach me a simple example of generating the 3SAT by using a small number? Let's say you are given ...
-2
votes
1answer
267 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 ...
13
votes
0answers
245 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
66 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
411 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
110 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}} + ...
6
votes
1answer
253 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
0answers
131 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
319 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 ...
22
votes
2answers
934 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 ...
27
votes
2answers
671 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 ...
18
votes
3answers
492 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 ...
9
votes
1answer
217 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
228 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 ...
21
votes
4answers
1k 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 ...
31
votes
3answers
1k 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 ...
10
votes
2answers
361 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 ...
21
votes
3answers
1k 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 ...
22
votes
2answers
1k 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 ...
7
votes
4answers
444 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
328 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 ...
19
votes
2answers
737 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 ...
7
votes
1answer
481 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$, ...
15
votes
2answers
836 views
-5
votes
1answer
2k 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?
