mersenneforum.org algorithms for special factorizations
 User Name Remember Me? Password
 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 1101010010112 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

B316 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 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)
2011-07-27, 21:32   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 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:

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

the zx part would cancel out on multiplication.

2011-07-28, 02:06   #7
wblipp

"William"
May 2003
New Haven

1001001110012 Posts

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.

 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 02:35.

Tue Apr 13 02:35:17 UTC 2021 up 4 days, 21:16, 1 user, load averages: 2.13, 2.36, 2.45