 mersenneforum.org algorithms for special factorizations
 Register FAQ Search Today's Posts Mark Forums Read 2011-07-26, 22:02 #1 jjcale   Jul 2011 22 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^57-4)) and factor (gcd(3^228+4,3^(3*57)-2*3^57+4))   2011-07-27, 00:42 #2 bsquared   "Ben" Feb 2007 2·33·61 Posts You're right - yafu doesn't search for algebraic factors. Look into tools like pari/gp or mathematica.   2011-07-27, 05:29   #3
Random Poster

Dec 2008

17610 Posts 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)   2011-07-27, 20:01 #4 jjcale   Jul 2011 22 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 142608 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)   2011-07-27, 21:32   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts 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:

the zx part would cancel out on multiplication.   2011-07-28, 02:06   #7
wblipp

"William"
May 2003
New Haven

92416 Posts Quote:
 Originally Posted by science_man_88 which goes back to: the zx part would cancel out on multiplication.
Only if you select z and y properly. The right side has a term of that you shouldn't ignore.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Raman Cunningham Tables 39 2020-08-28 14:34 wblipp Math 2 2010-08-15 20:33 Mr. P-1 GMP-ECM 5 2009-10-11 12:44 gd_barnes No Prime Left Behind 25 2009-07-30 12:06 J.F. Factoring 3 2008-06-14 18:58

All times are UTC. The time now is 21:48.

Mon Oct 19 21:48:02 UTC 2020 up 39 days, 18:59, 1 user, load averages: 1.44, 1.76, 1.87