For questions about finding factors of e.g. integers or polynomials

learn more… | top users | synonyms

22
votes
0answers
335 views

Irreducibility of $~\frac{x^{6k+2}-x+1}{x^2-x+1}~$ over $\mathbb Q[x]$

The Artin—Schreier polynomial $~x^n-x+1~$ is always irreducible over $\mathbb Q[x]$, unless $n=6k+2$, in which case it seems to have only two factors, one of which is always $x^2-x+1$. The ...
12
votes
0answers
181 views

Have I discovered an analytic function allowing quick factorization?

So I have this apparently smooth, parametrized function: The function has a single parameter $ m $ and approaches infinity at every $x$ that divides $m$. It is then defined for real $x$ apart ...
12
votes
0answers
599 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor $...
9
votes
0answers
122 views

Factorize: $a^3(b+c)+b^3(a+c)+c^3(a+b)$.

Factorize: $a^3(b+c)+b^3(a+c)+c^3(a+b)$. I found this question on a high school textbook but it seems impossible to be further factorized. The best I can get is: $a^3(b+c)+b^3(a+c)+c^3(a+b) = (a+b+c)...
7
votes
0answers
249 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 ...
6
votes
0answers
218 views

Reducing multivariate rational fractions to lowest terms

I wish to simplify multivariate rational fractions to a canonical form. Thanks to some very helpful mathematically inclined people who verified that my understanding of Wikipedia was correct, I'm now ...
5
votes
0answers
79 views

Does Pollard rho works for Gaussian integers?

Should I expect that the Pollard rho method ...
5
votes
0answers
315 views

proof that $\frac{x^p - 1}{x-1} = 1 + x + \dots + x^{p-1}$ is irreducible

I am reading the group theory text of Eugene Dickson. Theorem 33 shows this polynomial is irreducible $$ \frac{x^p - 1}{x-1} = 1 + x + \dots + x^{p-1} \in \mathbb{Z}[x]$$ He shows this polynomial ...
5
votes
0answers
184 views

Fastest Primality test using $N-1$ Factorization?

If $N-1$ could be factored easily with several small prime factors, then what is the fastest way to check $N$ for primality? Updated I'm aware of Pocklington primility test which is not good for ...
4
votes
0answers
49 views

Finding how large $p$ needs to be to have $n$ unique factors…

If we take a prime $p$, how large does $p$ have to be so that $p-1$ has at least $n$ factors between $f_1$ and $f_2$? (Note that the factors can be prime or composite) Note that I'm looking more for ...
3
votes
0answers
71 views

Can we continually factorize an expression like $x+y$?

I have a question that, for lack of familiarity or understanding of the relevant fields, I'm not quite sure how to formulate, so I'll just start off with an example and list some questions as I go. As ...
3
votes
0answers
36 views

What was Gauss' 2nd Factorization Method?

Reading Jean-Luc Chabert's A History of Algorithms, I learned that Gauss, prompted by the poor state-of-the-art, designed two distinct methods for fast integer factorization. Chabert's book discusses ...
3
votes
0answers
75 views

For any field $k$ and $n>0$: $X^n-a\text{ reducible }\ \Leftrightarrow\ a=b^p\ \vee\ a=-4b^4$.

I'm stuck on the following exercise: Let $k$ a field and $n$ a positive integer. Prove that $X^n-a\in k[X]$ is reducible if and only if there exist a prime $p$ dividing $n$ and a $b\in k$ such ...
3
votes
0answers
153 views

Probability distribution of the (size of the) smallest prime factor

Related question: Expected smallest prime factor Background: Given a toolbox of factorization algorithms (like trial division, ECM, quadratic sieve, GNFS) and a set of large composite numbers, I'm ...
3
votes
0answers
121 views

Symmetry in the Sum of Factors

The factors of 72 are 1,2,3,4,6,8,9,12,18,24,36,72. The factors can be organized as such $$m=1,2,3,4,6,8$$ $$n=72,36,24,18,12,9$$ Knowing the symmetric properties and that the 12 factors exist. Pair ...
2
votes
0answers
33 views

factoring polynomials in ring of integers modulo powerful number

I am having trouble finding info on how to factor polynomials in ring of integers modulo powerful number. For example: $x^2 - 1$ in $\textbf Z_{8}$. I know by tinkering around that $(x - 1)(x + 1)$...
2
votes
0answers
50 views

Factoring $x^5+B x^4+C x^3+D x^2+E x+F=(x^2+a x+b)(x^3+p x+q)$ over $\mathbb{Q}$

For a quntic polynomial to be reducible to the following form over $\mathbb{Q}$: $$x^5+B x^4+C x^3+D x^2+E x+F=(x^2+a x+b)(x^3+p x+q)$$ We need to match the coefficients ($a=B$ obviously, so we ...
2
votes
0answers
57 views

Easy method of determining if a polynomial over $\Bbb{Z}$ has any quadratic factors with rational coefficients

There is an easy method of determining whether a monic polynomial $$\sum_0^n a_k x^k$$ with all $a_k \in \Bbb{Z}$ and $a_n = 1$ has any integer roots. At least it is easy if you can factor the ...
2
votes
0answers
43 views

How Do I Apply the Cantor-Zassenhaus algorithm to $\mathbb{F}_2$?

Recently, I've been trying to implement the Cantor-Zassenhaus algorithm in C++ over $\mathbb{F}_2$. According to this lecture, the algorithm is basically: Input is polynomial $f\in\mathbb{F}_q$ with ...
2
votes
0answers
126 views

Finding roots and factors of multivariate polynomials

I know that in order to factor a one dimensional polynomial one can find the roots with some method, for instance a numerical newton method. Then one can systematically divide with $(variable-root)$ ...
2
votes
0answers
36 views

Factorization by multiplying and representation as difference of two squares

Definition 1.$$R: \mathbb N \to \mathbb N: \ R(n) = \lceil\sqrt{n}\rceil^2-n.$$ This is the distance from $n$ to the smallest square greater or equal to $n$. Definition 2. Let $a$ be as positive ...
2
votes
0answers
56 views

Factoring quaternion into three parts

I am faced with a problem where I have a quaternion which represents rotation and three arbitrary axis about which I can make rotations, thus three unit vectors. What I would like to know is angles (...
2
votes
0answers
285 views

A quick way to determine number of ring homomorphism

Find the number of ring homomorphism from $\mathbb Z_2\times \mathbb Z_2$ to $\mathbb Z_4$. I know that checking idempotent elements the number of ring homomorphisms is $1$. Again the number of ring ...
2
votes
0answers
34 views

About factoring trinomials over $\mathbb{Z}$

We were taught in school an algorithm to factor a trinomial of the form $$x^2\pm bx\pm c$$ with $b,c\in \mathbb{Z}^+$. Assuming the best scenario (that the polynomial has both roots in $\mathbb{Z}$),...
2
votes
0answers
66 views

Multiplication Sieving

Background I made another improvement to Fermat's sieve factorization, by merging the sieves groups of $4,3,5,7,11,13,17$ in two one big group. This method allows me to reduce the values that I need ...
2
votes
0answers
80 views

Show that $x^4+n(2-n)x^2+n^2$ reducible over Q for any natural number n.

Show that $$x^4+n(2-n)x^2+n^2$$ reducible over Q for any natural number n. Here is what I did $$x^4+n(2-n)x^2+n^2=x^4+2nx^2-n^2x^2+n^2=x^4+2nx^2+n^2-n^2x^2$$ $$=(x^2+n)^2-(nx)^2$$ $$=(x^2+n-nx)(x^2+...
2
votes
0answers
73 views

factor theorem for multivariables

My understanding of the remainder theorem for one variable is that for $$f(x)=(x-a)q(x)+r(x)$$$\qquad$ if $x=a\implies f(a)=0\times q(a)+r(a)$ so $f(a)=r(a)$ Is this correct for a multivariate ...
2
votes
0answers
93 views

Humankind knows the prime factorization of the first how many consecutive integers?

I am only looking for an approximation. I'm guessing the answer must be somewhere between $10^{20}$ and $10^{50}$. . Edit: Okay so my first initial estimation was pretty poor... I should have ...
2
votes
0answers
427 views

Proof for maximal ideals in $\mathbb{Z}[x]$

I have been trying to prove the following theorem: Every maximal ideal in $\mathbb{Z}[x]$ has the form $(p, f(x))$ where $p$ is prime integer and $f$ is primitive integer polynomial that is ...
2
votes
0answers
86 views

What is the line of thinking to get $[(n^2+3n+1)^2-5n(n+1)^2]$ from $(n^4+n^3+n^2+n+1)$?

There is this one little tiny step along the working that I don't quite understand, but I think it is better if I write the whole problem and solution for clarity. Problem: Factorise $5^{1995}-1$ ...
2
votes
0answers
29 views

Decomposability of a function into two

This is question on the existence of a decomposability of a function $f(v)$ into multiplicative factors $\lambda(v)$ and $g(v)$. The question is non-trivial since the functions $\lambda(v)$ and $g(v)$ ...
2
votes
0answers
122 views

Quadratic Diophantine Equations in Polynomial Time

Considering the problem of finding lattice points $(x_1, x_2 ... x_n)$ that satisfy a quadratic law: $F(x_1, x_2... x_n) = 0$ such that $F(x_1, x_2... x_n)$ is a second degree polynomial It is ...
2
votes
0answers
168 views

Prime factors of a random number

Let $r$ be a uniformly random integer between $1$ and $N$, for some large enough $N$ (i.e., I'm only interested in the asymptotics). What is the expected largest prime factor of $r$? Is there a good ...
2
votes
0answers
52 views

Different elliptic curves over given $\mathbb{F}_q$ can have different orders?

As the title says: For a given $q \in \mathbb{N}$, in $\mathbb{F}_q$, is it true that different curves on it can have different group orders? I assume yes. Let $q:=5$. Wikipedia gives $9$ points for $...
2
votes
0answers
100 views

Understanding of Pollard rho factorization

I am trying to better understand the ideas and intuition behind the Pollard Rho factorization algorithms. Given an $x_0$ and an irreducibe polynomial we can create a sequence from the recursive ...
2
votes
0answers
207 views

How many co-primes are there for a big integer N over a specified interval?

How many co-primes are there for a big integer $N$ over a specified interval ? bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ ...
2
votes
0answers
122 views

Factors of a polynomial in several variables

Fix an embedding of $\overline{\mathbb{Q}}$ into $\mathbb{C}$. Suppose you have a polynomial in several variables, with algebraic coefficients: $P\in \overline{\mathbb{Q}}[z_1, \ldots, z_n]$. Also ...
1
vote
0answers
15 views

Is it easy to factor if we know $k\phi(PQ)$?

Suppose we know $k\phi(N)=k\phi(PQ)=k(P-1)(Q-1)$ where in $N=PQ$ we have $P,Q$ being similar sized primes and $k\in\Bbb Z$ is unknown can we factor $N$ in polynomial time?
1
vote
0answers
24 views

Analog of Euler's Factorization method

One of Euler's discoveries was if an integer $n$ can be represented as a sum of two squares in two distinct ways, then one can factor $n$ explicitly. Of course, the method was ineffective as an ...
1
vote
0answers
30 views

Factor polynomial series with coefficients of 0 or 1?

Is there any easy way to factor polynomials which have coefficients of only $0$ or $1$ and always have a $+1$ ? For example, factor $9^{25}+ 9^{19}+ 9^{14}+ 9^9 + 9^6 + 9^5 + 1$
1
vote
0answers
77 views

Integer Factorization problem - New Idea

I been thinking about slightly different approach of solving the problem, and I want you to tell me if my idea is reasonable and if it's original(If someone already thought about this, I would be ...
1
vote
0answers
33 views

Grouping a set of numbers

I have a set of numbers which I don´t know if they belong to the same group (I could also call it factor or treatment, but actually each group is suppose to identify the same biological event). I am ...
1
vote
0answers
19 views

Cracking any linear congruential generator

I have a linear congruential generator $X_{n+1} = (aX_n + b) \bmod 2^k $with given arguments and number $Y$. The problem is to find the smallest $i$ that $X_i = Y$ or tell that there is no such $i$. ...
1
vote
0answers
37 views

ab = X mod Y (X and Y known)

Is there a better way to determine possibilities for $a \mod Y$ and $b \mod Y$ in the following equation: $ab = X \mod Y$ than by brute force? For example if $ab = 5 \mod 6$ then either $a = 1 \mod ...
1
vote
0answers
50 views

Proving that if $p(x)$ divides $f(x)g(x)$ then $p(x)$ divides $f(x)$ or $g(x)$

I need to somehow prove that if $p(x)$ is irreducible and divides $f(x)g(x)$ then $p(x)$ divides $f(x)$ or $g(x)$. I've been given the hints that I should use the theorems: $p(x)$ is irreducible ...
1
vote
0answers
26 views

factor $\sum_i^4 p_i x^i$

The polynomial $f(x)= \sum_{i=0}^4 p_i x^i $ whose real coefficients are: $$ p_4 = (L^2 + s^2) ^2 \\ p_3= -4 L^2 (L^2 + s^2)\\ p_2 = 6 L^4 + 2 L^2s^2 \\ ...
1
vote
0answers
36 views

Factorization of polynomial $f(x,y)$

The motivation is solving the following equations: $$ f(x,y)=0, x=L-kL, y=ks $$ $k$ is the variable, $L$ and $s$ are constants. The plan is: First, to factorize the polynomial as $(a_1x+b_1y+c_1) (...
1
vote
0answers
14 views

Complex filter factorizations with invariant points

Based on this question, using the same $z_0$: $$z_0 = e^{2\pi i / 8}$$ if we modify the sequence from previous question to look like this ($*$ denotes discrete convolution): $$\left(z_0^{[-2k,3k]} * ...
1
vote
0answers
19 views

Complex filter factorizations - continued

Continuing from this rather silly trivial question factoring real valued filters into shorter complex ones, hoping this won't be as trivial. If we modify it a bit: $$z_0 = e^{2\pi i / 8}$$ and $$\...
1
vote
0answers
21 views

Intrinsic Factorization with Modular Extension

The question here is has anyone seen a factorization algorithm similar to this? What is it called? Start with this $XY=N$. Suppose we know one non-trivial factorization of $N$, $X=x$ and $Y=y$. ...