algorithms for special factorizations

jjcale · 2011-07-26, 22:02

Are there algorithms that look for special factorizations ?

Example :
if n divides m^4 + 4*b^4
then
n divides (m^3 - 2*(b^2)*m - 4*b^3) * (m^3 - 2*(b^2)*m + 4*b^3)

yafu doesn't recognize this factorization (e.g. with m = 3^57 , b = 1) :
factor (3^228+4) takes much longer then
factor (gcd(3^228+4,3^(3*57)-2*3^57-4))
and factor (gcd(3^228+4,3^(3*57)-2*3^57+4))

bsquared · 2011-07-27, 00:42

You're right - yafu doesn't search for algebraic factors. Look into tools like pari/gp or mathematica.

Random Poster · 2011-07-27, 05:29

Quote:

Originally Posted by jjcale

Example :
if n divides m^4 + 4*b^4
then
n divides (m^3 - 2*(b^2)*m - 4*b^3) * (m^3 - 2*(b^2)*m + 4*b^3)

Or you could just use the fact that
m^4 + 4*b^4 = (m^2 + 2*b^2 + 2*b*m)*(m^2 + 2*b^2 - 2*b*m)

jjcale · 2011-07-27, 20:01

But how do I find for given n "simple" polynomials p and q (if they exist), such that n = p(m) * q(m) ?

fivemack · 2011-07-27, 20:06

In general, you can't. You do a load of factorisation of polynomials of simple form (as a product of polynomials), and sometimes you get lucky and find patterns like

x^4+64 = (x^2-4x+8) (x^2+4x+8)

science_man_88 · 2011-07-27, 21:32

Quote:

Originally Posted by fivemack

In general, you can't. You do a load of factorisation of polynomials of simple form (as a product of polynomials), and sometimes you get lucky and find patterns like

x^4+64 = (x^2-4x+8) (x^2+4x+8)

which goes back to:

$x^4+y^2 =x^2\pm {zx}+y$

the zx part would cancel out on multiplication.

wblipp · 2011-07-28, 02:06

Quote:

Originally Posted by science_man_88

which goes back to:

$x^4+y^2 =x^2\pm {zx}+y$

the zx part would cancel out on multiplication.

Only if you select z and y properly. The right side has a term of $(2y-z^2)x^2$ that you shouldn't ignore.

2011-07-26, 22:02	#1
jjcale Jul 2011 2² Posts	algorithms for special factorizations Are there algorithms that look for special factorizations ? Example : if n divides m^4 + 4b^4 then n divides (m^3 - 2(b^2)m - 4b^3) * (m^3 - 2(b^2)m + 4b^3) yafu doesn't recognize this factorization (e.g. with m = 3^57 , b = 1) : factor (3^228+4) takes much longer then factor (gcd(3^228+4,3^(357)-23^57-4)) and factor (gcd(3^228+4,3^(357)-2*3^57+4))

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Aurifeuillian Factorizations	Raman	Cunningham Tables	39	2020-08-28 14:34
Schinzel's Aurifeuillian style factorizations?	wblipp	Math	2	2010-08-15 20:33
Why do these P+1 factorizations work?	Mr. P-1	GMP-ECM	5	2009-10-11 12:44
Prime k-value density rating and factorizations	gd_barnes	No Prime Left Behind	25	2009-07-30 12:06
lower bounds on incomplete factorizations	J.F.	Factoring	3	2008-06-14 18:58

2011-07-27, 00:42	#2
bsquared "Ben" Feb 2007 110101001011₂ Posts	You're right - yafu doesn't search for algebraic factors. Look into tools like pari/gp or mathematica.

2011-07-27, 20:01	#4
jjcale Jul 2011 2² Posts	But how do I find for given n "simple" polynomials p and q (if they exist), such that n = p(m) * q(m) ?

2011-07-27, 20:06	#5
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 13×491 Posts	In general, you can't. You do a load of factorisation of polynomials of simple form (as a product of polynomials), and sometimes you get lucky and find patterns like x^4+64 = (x^2-4x+8) (x^2+4x+8)