Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [factoring]

The tag has no usage guidance.

2
votes
1answer
37 views

Decidability of factoring algebraic equations

Given an arbitrary algebraic equation, say for example the likelihood of the bernoulli distribution: $$\prod_{i}^{n}\theta^{x_i}(1-\theta)^{1-x_i}$$ And some arbitrary factorization constraints, say:...
3
votes
1answer
222 views

Is integer factorization reducible to subset sum?

Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm? We assume that we know the algorithm solving the problem of Subset ...
1
vote
2answers
35 views

Query regarding Integer factorization

Let us consider a product $P$ (whose factors we do not know). Given a base $b$, such that all the Modulus Residues are calculated using powers of $b$ w.r.t. $P$. For some (unknown) power $x$ we know ...
1
vote
1answer
114 views

Congruence of Squares for Factoring [closed]

After coming across the assertion that given $$ x^2 = y^2 \pmod n \\ x \neq \pm y \pmod n $$ we can then conclude that n factors into $$ n = \mathrm{gcd}(n, x-y) \mathrm{gcd}(n, x+y). $...
0
votes
0answers
42 views

Improving an integer factoring algorithm

I've written an algorithm for integer factorization (specifically RSA-like coprimes - products of two large primes, roughly of the same number of decimal digits) which is not based on QS, GNFS or any ...
5
votes
0answers
181 views

Reduce factoring to solving quadratic equations

The problem of solving quadratic equations is as follows: Suppose you are given a set of quadratic equations and are asked to find $0$-$1$ values for the variables such that all equations are ...
2
votes
1answer
88 views

How is integer factoring not in $P$?

Everyone keeps claiming that integer factoring is in $NP$ but I just don't get it... Even with the simplest algorithm (division with all integers up to $\sqrt{n}$) the complexity should be $\sqrt{n}\...
1
vote
1answer
58 views

Isomorphism of finite dimensional polynomial algebras over finite fields

For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, do we have an efficient way of checking whether there exists an algebra isomorphism between: $$\frac{\mathbb{F}_q[x]}{\...
0
votes
1answer
54 views

Proof Review: Integer Factorization is in NP

I want to prove that integer factorization is in NP I have a general idea of how to prove this, and was wondering if I could get a sanity check: I'll show it's in NP by using a non-deterministic TM ...
1
vote
0answers
122 views

Converting Ambiguous Grammar G to LL(1)

So I am in the process of learning about LL(1) grammar and converting an ambiguous one into LL(1). I know how to figure out if a grammar (G) is ambiguous, however, I am having trouble converting it to ...
1
vote
0answers
43 views

Is it possible to transform this grammar into LL(1)?

This is the original grammar: S -> ABe A -> ab | a | ϵ B -> b I did try left factoring and this is what I got: ...
1
vote
1answer
117 views

Complexity class of integer factorization

Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is ...
0
votes
1answer
68 views

General number field sieve is slower then exhaustive search for 'small' numbers?

In an attempt to understand the efficiency of the GNFS, I've been looking at runtimes. The calculations seem to indicate the GNFS runs slower than exhaustive search for smallish n. For example: ...
2
votes
1answer
37 views

Is the runtime for the general number sieve given in base 10, e or 2?

When the runtime of the GNFS is given as e^(64/9*b(log b)^2)^1/3, what base is the log? I'm assuming its e, but other options would obviously be 10 and 2.
1
vote
1answer
76 views

Is the prime factorization problem not an instance of the change making problem?

When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can ...
3
votes
1answer
31 views

Is there an alternative to full factorization for testing the Polya conjecture?

The Polya conjecture is a disproved conjecture that states over half the numbers less than any number has an odd number of prime factors. It first fails at $n = 906,150,257$, thus being a good example ...
3
votes
3answers
2k views

Complexity of finding factors of a number

I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division: For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ ...
4
votes
1answer
99 views

What is fastest algorithm for factoring out square from number

I have $n$-digit integer $N=a^2b$, $b$ is square-free. In other words, $a$ is maximal square which divides $N$. What is fastest known algorithm to find $a$? I can write algorithm of $O(n^2\sqrt{N})$ ...
0
votes
2answers
88 views

Without primes in $P$ does integer factorization lie in $coNP$?

In integer factorization we ask 'Given $N$ is there a $a\in[2,\sqrt{N}+1]$ such that $a|N$?'. Is the above problem in coNP because we know primes is in $P$? That is there is no such factor $a$ of $...
12
votes
2answers
979 views

Why is FACTOR in Co-NP?

I'm having trouble wrapping my head around the problems PRIME, COMPOSITE, FACTOR and how they're related in terms of complexity. I understand that PRIME has been shown to be in $P$ by the AKS ...
1
vote
1answer
142 views

What is more efficient: gcd(x,y) or brute force, when x and y are a very big numbers

I implemented the quadratic sieve algorithm as it's described in wiki. Most of the work of the algorithm is to determine if some big integer $Y$ belongs to the vector $b[b_1,b_2,b_3,\ldots]$. So far ...
6
votes
4answers
2k views

Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and ...
16
votes
2answers
1k views

Why is factoring large integers considered difficult?

I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ ...
1
vote
1answer
71 views

Consequences of factoring and discrete log in $P/Poly$

What is the consequence of factoring and discrete log being in $P/poly$?
2
votes
1answer
54 views

A factoring conversion

There was a comment here that " It is possible in principle to reduce the factorization of a $256$-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension $N\times N$ where $...
3
votes
1answer
184 views

Devising an Algorithm for Linear Combination with Column Restrictions

Application: We intend to factor an integer $N$ using a variation of the rational sieve. This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ ...
2
votes
1answer
70 views

Does there exist a problem that is hard to do in parallel? [closed]

I am looking for a workload which is hard to paralellise/distribute between multiple machines. For example, integer factorization does not go 10 times faster if you have 10 machines to split the ...
0
votes
1answer
50 views

Integer factorization: comparing with floor

While working on integer factorization algorithm I came to the next problem: $$\frac{a}{ex} = \lfloor{\frac{a}{ex}\rfloor} + c$$ $a$ the number I want to factor $x$ factor of $a$ $e$ positive ...
0
votes
1answer
62 views

Finding three factors of a number with minimal sum

Suppose that we have a number $x \in \mathbb{Z}^+$. I am seeking an algorithm to find three numbers $a, b, c \in \mathbb{Z}^+$ such that $a \times b \times c = x$ and $a + b + c$ is minimum. Is this ...
1
vote
2answers
292 views

What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

I am aware that as the number increases in Digits the process of locating the two prime numbers that when multiplied produce the given number is increased as well. I also know that is it somewhat ...
2
votes
1answer
163 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
90 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
108 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
75 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
72 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, e.g.,...
0
votes
2answers
36 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
172 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 ...
2
votes
2answers
2k 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}$ works. ...
8
votes
2answers
3k 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 ...
6
votes
2answers
408 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
376 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
196 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 ...
5
votes
0answers
605 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 ...
6
votes
1answer
1k 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
103 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 ...
3
votes
2answers
392 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 ...
6
votes
1answer
140 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
268 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
102 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 ...
14
votes
2answers
2k 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 ...