The factoring tag has no wiki summary.
2
votes
1answer
43 views
Generating 3SAT circuit for Integer factorization example
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
0answers
54 views
Karp reduction between FACTORING and a variant of it
Consider the following variant of the FACTORING problem (given N,M decide whether N has a prime factor less than M):
MULTIPLE-FACTORING: Given three integers $1 \leq K \leq M \leq N$ decide if there ...
1
vote
1answer
52 views
Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$
I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time ...
3
votes
0answers
49 views
How hard is it to factorize sum of two numbers
Say I have numbers with known factorizations $n = \prod \limits _i p_i ^{n_i}$ and $m = \prod \limits _i p_i ^{m_i}$ (where $p_i$ is the $i$th prime).
How hard is it to factorize $m+n$? Is there a ...
3
votes
2answers
115 views
Number of digits in a binary product
Assume i have 2 numbers in binary form (or, more precisely, assume to know the number of their digits, DF1, DF2):
101010101001010101010101010111111111111111111111010101
10101111111111111111010101
Is ...
2
votes
2answers
49 views
Optimization-factoring $\le_p$ Decision-factoring
Optimization factoring:
Input: $N\in \mathbb{N}$
Output: All prime factors of $N$
Decision factoring:
Input: $N, k\in \mathbb{N}$
Output: True iff $N$ has a prime factor of at most $k$
How can I ...
7
votes
2answers
204 views
How can P =? NP enhance integer factorization
If ${\sf P}$ does in fact equal ${\sf NP}$, how would this enhance our algorithms to factor integers faster. In other words, what kind of insight would this fact give us in understanding integer ...
5
votes
2answers
175 views
Reducing the integer factorization problem to an NP-Complete problem
I'm struggling to understand the relationship between NP-Intermediate and NP-Complete. I know that if P != NP based on Lander's Theorem there exists a class of languages in NP but not in P or in ...
7
votes
1answer
116 views
Can top SAT-solvers factor easy numbers?
Modern SAT-solvers are very good at solving many real-world examples of SAT instances. However, we know how to generate hard ones: for instance use a reduction from factoring to SAT and give the RSA ...
2
votes
2answers
169 views
Is it possible to use dynamic programming to factor numbers
Let's say I am trying to break all the numbers from 1 to N down into their prime factors. Once I have the factors from 1 to N-1, is there an algorithm to give me the factors of 1 to N using dynamic ...
