mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-07-26, 22:02   #1
jjcale
 
Jul 2011

22 Posts
Question 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))
jjcale is offline   Reply With Quote
Old 2011-07-27, 00:42   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·33·61 Posts
Default

You're right - yafu doesn't search for algebraic factors. Look into tools like pari/gp or mathematica.
bsquared is offline   Reply With Quote
Old 2011-07-27, 05:29   #3
Random Poster
 
Random Poster's Avatar
 
Dec 2008

17610 Posts
Default

Quote:
Originally Posted by jjcale View Post
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)
Random Poster is offline   Reply With Quote
Old 2011-07-27, 20:01   #4
jjcale
 
Jul 2011

22 Posts
Default

But how do I find for given n "simple" polynomials p and q (if they exist), such that n = p(m) * q(m) ?
jjcale is offline   Reply With Quote
Old 2011-07-27, 20:06   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

142608 Posts
Default

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)
fivemack is offline   Reply With Quote
Old 2011-07-27, 21:32   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-07-28, 02:06   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

92416 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
wblipp is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.