# Tagged Questions

The tag has no usage guidance.

18 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 ...
47 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$ ...
63 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})$ ...
49 views

84 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$$ ...
57 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 ...
41 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 ...
34 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 ...
138 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 ...
129 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 ...
75 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 ...
102 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 ...
58 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 ...
62 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.,...
33 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 ...
136 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 ...
983 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}$ ...
750 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 ...
246 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 = \...
218 views

1k 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 NP-...