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

learn more… | top users | synonyms

13
votes
0answers
202 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 ...
10
votes
0answers
331 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 ...
8
votes
0answers
115 views

Is there an easy way to factor polynomials with two variables?

On a recent precal test, I saw a question involving the following expression: $$(x+1)^2-y^2$$ Which factored out into: $$(x+y+1)(x-y+1)$$ This wasn't very hard, considering that it was already ...
5
votes
0answers
172 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 ...
5
votes
0answers
205 views

Carmichael number factoring

The task I'm faced with is to implement a poly-time algorithm that finds a nontrivial factor of a Carmichael number. Many resources on the web state that this is easy, however without further ...
4
votes
0answers
81 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 ...
3
votes
0answers
106 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
101 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 ...
3
votes
0answers
118 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 ...
2
votes
0answers
24 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
48 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
34 views

Does this approach for factorizing RSA numbers help in any way?

I was thinking about why factorizing RSA numbers is so hard. When humans perform any kind of maths manually, they often employ various 'tricks' that get them closer to the answer. Some are based on ...
2
votes
0answers
78 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
49 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
84 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
81 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
24 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
107 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
113 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
51 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
181 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
105 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
37 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 ...
1
vote
0answers
31 views

Finding the factors of integer x and its square

What is the the theorem or property that says that $\forall{}x\in{}Z$, the set of all integers, $x^2$ has the same factors as $x$, twice?
1
vote
0answers
17 views

Splitting field of a cubic polynomial understanding

The cubic polynomial $f(x) = x^3+px+q\in K[x]$ has 3 roots $a_1,a_2,a_3\in \mathbb C$ Hence, the splitting field extension $L=K(a_1,a_2,a_3)$ $\delta=(a_1-a_2)(a_1-a_3)(a_2-a_3)\in L$ since ...
1
vote
0answers
20 views

Factorising Complex Polynomial with Complex Coefficients

I have tried to factorise the polynomial in question 19 by using the factor theorem to find other factors, however this has been unsuccessful thus far. Seeing as the conjugate root theorem does not ...
1
vote
0answers
32 views

When looking at the mod as binary value

Look at the next value: $$617*947 = 584299$$ 617, 947 are prime values. I want to see what are all the possible solutions for the next equation, for $k=4$: $$(a\mod k)(b\mod k) = 584299\mod k$$ ...
1
vote
0answers
37 views

When $\frac{-1436+y\pm \sqrt{(1436-y)^2 - 4\cdot480547}}{-2}$ is integer

While working on my algorithm I came to this problem: $$x_{1,2} = \frac{-b-a+y \pm \sqrt{(b + a-y)^2 - 4c}}{-2}$$ $$x_1 = \frac{c}{x_2}$$ $a,b,c$ are positive known integers $y$ is positive integer ...
1
vote
0answers
18 views

Should this be rephrased into saying no common factors but 1?

This is from Discrete Mathematics and its Applications For the phrase "a and b have no common factors" , does that actually mean a and b have no common factors other than 1? I feel like this would ...
1
vote
0answers
55 views

Findind 3 factors for a integer number

As a background I'll explain what I'm trying to achieve and where's from. In Person of Interest, a TV series, one of the characters gets a phone number in the form of area code and phone number, like ...
1
vote
0answers
86 views

Factoring a polynomial over $\mathbb F_{2^8}$

How do you find the factors of $x^4+x+1$ in $GF(2^8)$ in terms of polynomials? Let me explain, We have primitive irreducible polynomial $p(x)=x^2+x+1$ in $GF(2^2)$ which has root $\alpha^2+\alpha$ in ...
1
vote
0answers
36 views

Numbers with special factorisation

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all ...
1
vote
0answers
50 views

Binary Polynomial Factoring

I just need confirmation that I've done my math right. If $a(x) = x^4 + x^3 + x + 1$ and $b(x) = x^2 + x + 1$ are binary polynomials, find binary polynomials s(x) and r(x) such that $x^4 + x^3 + x + ...
1
vote
0answers
22 views

Finding coefficients of the min polynomial of an $n\times n$

Given an $n\times n$ matrix, for ease assume this matrix is over the $F_m$. What we know about min poly is the the non-zero components of the min polynomial for this case, ie if there is $x^2$, or ...
1
vote
0answers
24 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
0answers
144 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 ...
1
vote
0answers
16 views

By what factor do winning chances increase based on total value?

Say I am entering 24/7 in endless sweepstakes, contests, giveaways, drawings, etc. Assuming each one I enter has no less than 1 in 1,000 chances, but no more than 1 in 1 million (and I enter at least ...
1
vote
0answers
45 views

On number of different factorizations over integers of a number field

Let $K$ be a finite field extension of the rational numbers and let $\mathcal{O}_K$ denote its ring of integers. If a rational integer $n$ factors into two distinct ways into irreducible elements in ...
1
vote
0answers
73 views

How are the general skills for complete factorization of arbitrary homogeneous order polynomials in $\mathbb{C}$?

How are the general skills for complete factorization of arbitrary homogeneous order polynomials in $\mathbb{C}$ ? For example: $1.$ $a^2+b^2+c^2$ $2.$ $a^2+b^2-c^2$ $3.$ $a^2+b^2+c^2+d^2$ $4.$ ...
1
vote
0answers
453 views

Find the set of cyclotomic cosets of q modulo n

Calculating finite field and factoring $x^n - 1$ over $GF(q)$ first step is to calculate cyclotomic cosets. For example : For $n=9,q=2$ $C_1=\{1,2,4,8,7,5\} = C_4 = C_8 = C_7 = C_5$ $C_3=\{3,6\} ...
1
vote
0answers
444 views

Finding irreducible polynomials and factorization

Need some explanation and checking if my thinking on the solution is correct for the assignment given below: (In these problems you may use without proof which polynomials of degree 2 and 3 are ...
1
vote
0answers
42 views

Given a cubic $f(x)$ with specified negative real roots $-a,-b,-c$, what happens when we search for solutions to $f(x)=d$?

Noting Roots of a Certain type of Cubic Equation, what if we have the following simpler form for real $d$: $$(x+a)(x+b)(x+c)=d\tag{1}$$ (With $a,b,c\in \mathbb R^+$.) Clearly, depending on $d$, the ...
1
vote
0answers
75 views

Parametric Equation solving over integers

I have a question on my mind I am trying to solve. However I am stuck at a point. If you could help, I would be very pleased. $$\frac {x_2y_2z_2}{x_2y_2+y_2z_2+x_2z_2}=\frac ...
1
vote
0answers
56 views

Integer factorization using discrete logarithms

I'm reading up on RSA and attacks on it. At the end of one section of the notes, it asks (without giving an answer) whether or not integer factorization is easy given an oracle which computes discrete ...
1
vote
0answers
761 views

Factorization of cyclic polynomial

Factorize $a(b^2-c^2)+b(c^2-a^2)+c(a^2-b^2)$ Since this is a cyclic polynomial therefore factors are also cyclic : $f(a) = a(b^2-c^2)+b(c^2-a^2)+c(a^2-b^2)$ $f(b) = b(b^2-c^2)+b(c^2-b^2)+c(b^2-b^2) ...
1
vote
0answers
127 views

What is the condition for a polynomial to be factorizable in linear real factors?

I have a polynomial $p_a(x,y)= x^2F(a)+y^2G(a)-xH(a)-I(a)$ where $F(a)$, $G(a)$, $H(a)$ and $I(a)$ some real fuctions of $a$ are. Which conditions must satisfy $a$ so that I can factorize the ...
1
vote
0answers
87 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 ...
1
vote
0answers
138 views

A special factorization

Suppose that monic polynomial $f(x)\in\Bbb Z[x]$ such that for all $m\in\Bbb Z$, $m>1$, there's no integers $\langle r,r_1,\ldots,r_m\rangle$ such that $f(r)=f(r_1)\cdots f(r_m)$. Is there any ...
1
vote
0answers
105 views

Is there a name for a number whose factors' exponents are all prime?

For instance, 864, whose factorization is 2^5 x 3^3.
1
vote
0answers
288 views

Factoring multivariate polynomials

If I have a multivariate polynomial $P[X_1,\dots,X_n]\in \mathbb{R}[X_1,\dots, X_n]$, is there a polynomial time algorithm to factor the polynomial into irreducible polynomials $\in ...