# Tagged Questions

20 views

### Factorisation algorithm for polynomials in several variables over $\mathbb{Z}$.

What algorithm is used by a CAS to decide how to factor a polynomial in several variables over $\mathbb Z$?
44 views

### Efficient factorization of numbers with unique prime factors

I need a factorization algorithm for numbers of the form $n = p_{1}p_{2}\cdots p_{k}$ with $p_i \neq p_j$ for $i \neq j$ and $p_j \in \{p : p \mbox{ is a prime and } p \leq P_s\}$, where $P_s$ is the ...
50 views

### Complexity of factoring non-squarefree numbers

Consider the two numbers $N_1=p_1\cdot p_2$ and $N_2=p_1^2\cdot p_2$, where $p_1$ and $p_2$ are primes. Is there any factoring algorithm that can factor $N_2$ faster than the asymptotically fastest ...
93 views

103 views

### Why does Lenstra ECM work?

I came across Lenstra ECM algorithm and I wonder why it works. Please refer for simplicity to Wikipedia section Why does the algorithm work I NOT a math expert but I understood first part well enough ...
154 views

### Pattern in Fermat Factorization

I have the Fermat Factorizations of $n = pq$ where $p$ and $q$ are primes. I am trying to find a formula/pattern for the number of cycles required to perform the factorization in terms of $n, p, q$. ...
2k views

### Pollard-Strassen Algorithm

I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...
267 views

### Roots of rational equation with multiple variables?

Let's say we have a rational polynomial in $k$ variables. We are only interested in rational solutions. If $k = 1$, name the variables ${x}$, if $k = 2$, name them ${x,y}$. For $k = 1$, it can be ...
265 views

### Determine the number of factors for extremely large numbers.

An offshoot from a related question, is there a way to determine the number of possible factors (odd, even, prime, etc.) for extremely large integers without actually factoring them? Even an ...
256 views

### Finding the radical of an integer

Given a number $x = p_1^{e_1}\cdots p_n^{e_n}$ with different primes $p_i$ and exponents $e_i \ge 1$, is there an efficient way to find $p_1\cdots p_n$? I ask this because for polynomials it's ...
133 views

### What are the specifics and the possible outputs of Pollard's Rho algorithm?

I'm trying to implement a simple prime factorization program (for Project Euler), and want to be able to use Pollard's Rho algorithm. I read the Wikipedia, wolfram|alpha, and planet math explanations ...
402 views

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors? For example, suppose we have $n = p * q = 167653$; in this case, $p = 359 = 101100111_2$ and $q = 467 = ... 1answer 95 views ### Factoring short intervals There are algorithms (e.g., SIQS) that factor individual numbers. For large ranges of numbers, sieving is more efficient: for example,$(x^2,x^2+x)$can be factored in time roughly linear in$x$. ... 1answer 226 views ### Factoring some integer in the given interval Let N be a positive integer. Is there an efficient (i.e. probabilistic polynomial time) algorithm which, on input a sufficiently large N, outputs the full factorization of some integer in the interval ... 4answers 681 views ### How to determine in polynomial time if a number is a product of two consecutive primes? How to determine in polynomial time if a number is a product of two consecutive primes? All I can figure out is that if CramÃ©r's conjecture is true, then we can use the AKS primality test to find ... 2answers 487 views ### Is the factorization problem harder than RSA factorization ($n = pq$)? Let$n \in \mathbb{N}$be a composite number, and$n = pq$where$p,q$are distinct primes. Let$F : \mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$(*) be an algorithm which takes as an input$x ...
Suppose you are given a number $n$ and told that the sum of its prime factors is $s$. I'm looking for an efficient algorithm that checks the truth of the statement. Obviously one can simply ...