1
vote
0answers
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$?
1
vote
1answer
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 ...
4
votes
1answer
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 ...
1
vote
2answers
93 views

Factoring any single-variable polynomial in $\mathbb C$

The fundamental theorem of algebra says $$ \forall p(x):\mathbb C \to \mathbb C,\ p(x) = a\prod_{n=0}^m\big(b_nx+c_n\big) $$ where $p(x)$ is a single-variable polynomial, and $\{a;m\}\cup\{\forall ...
2
votes
3answers
10k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
2
votes
1answer
69 views

Can the Euclidean algorithm fail by not terminating in non Euclidean domains?

Is it possible for the Euclidean algorithm to fail by not terminating in finite time in non-Euclidean domains? In $\mathbb{Z}[X]$ it can fail by going out of the ring, ie one gets a non integer ...
4
votes
1answer
153 views

Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?

The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all? With the ...
0
votes
1answer
32 views

Distinct-degree factorization

I'm trying to understand distinct-degree factorization from Wikipedia. I'm trying the algorithm on paper with $q=9$ and $f(x) = (x+4)(x+5) = x^2+2 \in F_{q}$. We start with $i=1$. I calculate $g = ...
3
votes
0answers
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 ...
0
votes
3answers
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$. ...
8
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
2answers
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 ...
5
votes
1answer
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 ...
0
votes
2answers
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 ...
4
votes
1answer
402 views

Is it possible to efficiently factor a semiprime given a bit-permutation relating the factors?

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 = ...
2
votes
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$. ...
6
votes
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 ...
8
votes
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 ...
6
votes
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 ...
2
votes
2answers
128 views

Calculations with liars and sums of prime factors

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 ...
21
votes
2answers
1k views

Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...