The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
76 views

Is FACTORIZATION or PRIMES known to be in LOGSPACE

Are the integer factorization and PRIMES known to be in LOGSPACE? Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known ...
3
votes
1answer
41 views

Does FACTORING have optimal substructure or analog to it?

Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily ...
1
vote
1answer
51 views

What are the current known implications of the complexity of Integer Factorization?

According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP. However, do we know any other ...
0
votes
1answer
38 views

efficient algorithms for factoring polynomials [closed]

Does anyone know what are the most efficient algorithms for factoring polynomials in a field of characteristic zero, i.e, a field that may contain infinitely many elements. I'm mainly concerned within ...
2
votes
1answer
40 views

Checking whether a number is a square or higher power modulo n

Is there an algorithm to check whether an integer $x$ is a square modulo $n$, where $n$ is an integer whose factorization we do not know? Is the Jacobi symbol helpful? What about higher powers, ...
0
votes
2answers
30 views

Proof for factors of a number

I was trying to prove the following: if x%(x/2) != 0 or x%(x/2) == 0 then x%(x/y) != 0 or x%(x/y) == 0 such that y = [2,4) So I am trying to figure out ...
3
votes
1answer
64 views

Complexity of factoring products of distinct prime numbers

Problem: Input is an integer number $x$ that we know factors as $p_{i_1}\cdot p_{i_2}\ldots p_{i_n}$, where the $p_{i_j}$'s are distinct prime numbers. Output is the above factorization of $x$. Do ...
3
votes
2answers
410 views

CNF Generator for Factoring Problems

I've been reading these: Fast Reduction from RSA to SAT CNF Generator for Factoring Problems (Also have C code implementation) I don't understand how the reduction from FACT to $3\text{-SAT}$ ...
1
vote
2answers
251 views

Shor's Algorithm speed

I'm a fledgling computer science scholar, and I'm being asked to write a paper which involves integer factorization. As a result, I'm having to look into Shor's algorithm on quantum computers. For ...
3
votes
1answer
139 views

integer factoring using Fermat's method

Reading an article on integer factorization I implemented the following - rather inefficient - factorization method: Every odd composite can be factored as a difference of squares: $$ ab = ...
3
votes
1answer
106 views

Are there problems that are polynomial-time equivalent to factoring composites?

It seems that factoring a number known to be composite is in its own interesting little complexity class, e.g. polynomial time using quantum computing even though no one has proved $\mathsf{P} = ...
5
votes
1answer
142 views

How hard is factoring a complex number?

Given complex number $C=a+ib$, I want to find two complex numbers $C_1=x+iy$ and $C_2=z+iw$ such that $C=C_1*C_2$ (a,b,x,y, z and w are all non zero integers). This problem is at least as hard as ...
3
votes
0answers
225 views

Time complexity of finding the largest factor of a number (using a specific oracle)

My question is related to this question posted on math.SE: Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper ...
3
votes
1answer
265 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
68 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 ...
2
votes
2answers
141 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 ...
5
votes
1answer
89 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
231 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
60 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 ...
9
votes
2answers
578 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 ...
8
votes
2answers
581 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 ...
10
votes
1answer
228 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
348 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 ...