20110726, 22:02  #1 
Jul 2011
2^{2} Posts 
algorithms for special factorizations
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^574)) and factor (gcd(3^228+4,3^(3*57)2*3^57+4)) 
20110727, 00:42  #2 
"Ben"
Feb 2007
2·3^{3}·61 Posts 
You're right  yafu doesn't search for algebraic factors. Look into tools like pari/gp or mathematica.

20110727, 05:29  #3 
Dec 2008
176_{10} Posts 

20110727, 20:01  #4 
Jul 2011
2^{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) ?

20110727, 20:06  #5 
(loop (#_fork))
Feb 2006
Cambridge, England
14260_{8} 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^24x+8) (x^2+4x+8) 
20110727, 21:32  #6  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
the zx part would cancel out on multiplication. 

20110728, 02:06  #7 
"William"
May 2003
New Haven
924_{16} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Aurifeuillian Factorizations  Raman  Cunningham Tables  39  20200828 14:34 
Schinzel's Aurifeuillian style factorizations?  wblipp  Math  2  20100815 20:33 
Why do these P+1 factorizations work?  Mr. P1  GMPECM  5  20091011 12:44 
Prime kvalue density rating and factorizations  gd_barnes  No Prime Left Behind  25  20090730 12:06 
lower bounds on incomplete factorizations  J.F.  Factoring  3  20080614 18:58 