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

learn more… | top users | synonyms

19
votes
0answers
298 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
568 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
116 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) = ...
7
votes
0answers
244 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
211 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
77 views

Does Pollard rho works for Gaussian integers?

Should I expect that the Pollard rho method ...
5
votes
0answers
304 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
183 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
47 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
31 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
149 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
120 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
37 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
29 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
105 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
33 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
50 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
225 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
33 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 ...
2
votes
0answers
63 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
79 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$$ ...
2
votes
0answers
66 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
384 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
85 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
120 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
157 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
99 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
204 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
117 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
28 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
70 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
28 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
16 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
36 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
49 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
35 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
18 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
20 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$. ...
1
vote
0answers
30 views

Factoring Algorithm Using Multilinear Forms

I was wondering if anyone could identify for me a known name for this algorithm, I would appreciate it. I will give an example. Let $N=961$. Then write $(6x+1)(6y+1)=6(160)+1$ Where $0<x\le y$ ...
1
vote
0answers
46 views

Reason for the method of factorization of cyclic expressions.

For example, I am given that factorize: $$a^2b+a^2c+ab^2+2abc+ac^2+b^2c+bc^2$$ So by the traditional method, we take the powers of $a$ $$=a^2(b+c)+a(b+c)^2+bc(b+c)$$ $$=(b+c)(a^2+ab+ac+bc)$$ ...
1
vote
0answers
36 views

Factor out factorial from expression

I have the expression $(k+1)! - 1 + (k+1)(k+1)!$ How do I factor out $(k+1)!$ to achieve the result: $[(k+1)!(k+2)] - 1$? I for the life of me cannot figure this out. Thanks!
1
vote
0answers
15 views

How can I factorize $|z_1|^q z_1 - |z_2|^q z_2$?

Let $1\le q\le 2$. I would like to know that how I can factorize the following: $$ |z_1|^q z_1 - |z_2|^q z_2 = \\(z_1 - z_2) (\text{ a function of } z_1, z_2, \overline{z_1}, \overline{z_2}, q ) + ...
1
vote
0answers
39 views

Notation for indexing the factorizations of a number?

Background Given any $n \in \mathbb{N}$, the ordered factorization count of $n$ can be computed and is traditionally written $H(n)$. This is, essentially, the number of unique decompositions of $n$ ...
1
vote
0answers
43 views

Factorizing a Polynomial over the Integers

What are the most efficient algorithms to factorize a polynomial over integers, knowing that it has only integer roots? I googled around a lot, but most of the work seems to be around Finite fields. ...