mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-05-04, 16:16   #1
jchein1
 
May 2005

748 Posts
Default Odd perfect related road blocks II

Alex, fivemack, ATH, Andi47, Andi HB & all other factoring specialists,


Let M be a smallest product of odd primes such that

square free of ( gcd ( f(x) ,g(x)) ) | M

for all integer x > 1 , where f(x) and g(x) are two given relatively prime integral polynomials. For example,


if f(x) = (x2 + x + 1)3 - 33 & g(x) = x6 + x3 + 1 = 0,

then M = 3 * 19 * 163


if f(x) = ((x4 + x3 + x2 + x + 1)5 - 55 ) /(x4 + x3 + x2 + x + 1 - 5 ) &

g(x) = x20 + x15 + x10 + x5 + 1,

then M = 5 * 151 * 701 * 2551 * 24251 * 34651 * 144853351 * 659575601 * 1271785993801.

By applying successive (my) extended Eculid algorithms, I have encountered if

1) f(x) = (x2 + x + 1)3 – 33 & g(x) = (x162 + x81 + 1)3 – 33 , then

Code:
M = a * 598644007623271861103907634394401713031280184082045961436816127153183697504366019739512180572430920157281903457051081235141165004401529332661832140639096711933077
(c162, 2900 curves done),

2) f(x) = ((x2 + x + 1)9 - 39 ) / ((x2 + x + 1)3 - 33 ) & g(x) = x162 + x81 + 1
then
Code:
M = b * 142255953422080949010042135770532701808988159571292214113059412169543088033374620681986196789531788565741609436257609136785819948534868895759387087438788760412860551
(c165, 2500 curves done ),

where a and b are products of known primes, c162 and c165 are two critical roadblocks I am unable to complete by myself.

Note that: these M‘s are part of my “pushing “ algorithms concerning several ongoing papers (first one is “On the divisibility of systems of cyclotomic polynomials of degrees 3 and 5”) . Alex may be familiar with c162 and c165 at certain degrees. I sincerely hope it will get completed this time, otherwise one of my lemmas will get killed. Can someone please kindly look into it or give a try before I finally give up.

I also found c1.x + c0 = 0 (mod c162), where
Code:
c1 =  69267298939868734352823569242638987830151794956582757323663257304713979808535979493103174703607420534575191258096981359057081634837910521017237222985183216764829376
c0 =  90396638571991941300717867224156466586094273057103180468944748956569143785197229469169728666741827825163688170928805513389627480981342184801410418423802620496945754
c1.x + c0 = 0 (mod c165), where
Code:
c1 =  76753267437136028631737826218354419681592252499734800494051831532232913505065057592910545783967666343514329739056408237901354351164460723435804959401745218854773
c0 = 209851117037629231974563829915727038069629516190909815572098319849496046563710374917531353670135870468192288676994164729691076296875290909453103109496164911219198
Is this helpful?



I am looking for one factor(only) from each of the following. Some of them may have posted before *, although these composites did not affect the proof, they caused me a lot of unnecessary work, please help and thank you in advance.

1) σ(59345478426821800746377014559617^4) = 3538361.c121 #
2) σ(99995282631947^10) = 23.c139
3) σ(62060021^18) = c141 * =2859153813495302135105360393 * 65219432427202213218611042380245134951516556220905814475152737256300473009279433432471898046319778085284772450023 (mklasson, ecm)
4) σ(347568611538691^10) = 23.617.683.692539.c133
5) σ(10177286401^12) =15731.c116 *
6) σ(6294091^22) = c150 *
7) σ(5229043^22) = 967.194443.c140 *
8) σ(846041103974872866961^6) =1709.c123 = 1709 . 5155723754893919994283900206097487201 . 41621437657162669816374890034224257842979191889517024692601717156897218627524115006963 (fivemack, ecm)
9) σ(934415109937^12) = 2549.c141 = 2549 . 2636398433195487889353395293207 . 65932167085234904931409415588486535060018564833464183835891750325639105962353333551790922471214875173575350927 (mklasson, ecm)
10) σ(P82^2) = 61.433.4651.156817.c150 *, where P82=
3404253904642598840161913302701587626837449819596812423232352
24442734524 2057474631
11) σ(797161^28) = 59.31727.c159
12) σ(172545754771028210096747645881^6) = 631.c173
13) σ(172827552198815888791^6) = 113.c120 = 113 . 3335162523320119257180081115662029635417481 .
70710259042622884083135682057512365547361929153437894550723481191426825243649 (fivemack, snfs)

14) σ(177635683940025046467781066894531^4) = 5.431.c126

* - most wanted
& - Alex resolved half a dozen and wblipp got one last year.
# - I completed at least several hundreds or even thousand curves per each composite a year ago but lost the record.

Best regards

Joseph

Last fiddled with by fivemack on 2009-05-05 at 00:30
jchein1 is offline   Reply With Quote
Old 2009-05-04, 17:02   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Joseph,

I made some typographical changes to fix the exponents and to avoid horizontal scrolling. Can you please check that I didn't introduce any errors?

Alex
akruppa is offline   Reply With Quote
Old 2009-05-04, 17:08   #3
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by jchein1 View Post
1) σ(59345478426821800746377014559617^4) = 3538361.c121 #
You seem to have missed a p11: 68280416627. It leaves a c110.

Quote:
Originally Posted by jchein1 View Post
5) σ(10177286401^12) =15731.c116 *
13) σ(172827552198815888791^6) = 113.c120
These are both difficulty ~120 via a sextic. I suggest you factor them yourself. They should be easy.

Last fiddled with by 10metreh on 2009-05-04 at 17:14
10metreh is offline   Reply With Quote
Old 2009-05-04, 17:22   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by 10metreh View Post
These are both difficulty ~120 via a sextic. I suggest you factor them yourself. They should be easy.
You sound like you know a lot about factoring and stuff! Can you please explain how you make a sextic for the second number?

Curiously yours,
Alex
akruppa is offline   Reply With Quote
Old 2009-05-04, 17:25   #5
mklasson
 
Feb 2004

2×3×43 Posts
Default

Quote:
Originally Posted by 10metreh View Post
You seem to have missed a p11: 68280416627. It leaves a c110.
You seem to have miscalculated. That p11 is not a factor.
mklasson is offline   Reply With Quote
Old 2009-05-04, 17:26   #6
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by akruppa View Post
You sound like you know a lot about factoring and stuff! Can you please explain how you make a sextic for the second number?

Curiously yours,
Alex
Sorry if I was making a mistake, but I was simply diving out the factor x - 1 from x^7 - 1 to get the polynomial x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 with root 172827552198815888791.

(Yes, you are more experienced than me, so you are giving me advice if you correct me.)

And about the p11 issue: I'm not sure. I probably had a typo in the input.

Edit: found the typo. I missed out a digit in the number

Last fiddled with by 10metreh on 2009-05-04 at 17:34
10metreh is offline   Reply With Quote
Old 2009-05-04, 17:41   #7
mklasson
 
Feb 2004

2×3×43 Posts
Default

p31=2636398433195487889353395293207 | sigma(934415109937^12) / 2549 with cofactor p110.
mklasson is offline   Reply With Quote
Old 2009-05-04, 17:48   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Ok, I understand that you want to factor the resultant of f(x) and g(x), for example

Code:
? f1(x) = (x^2+x+1)^3 - 3^3
? g1(x) = x^6 + x^3 + 1
? factorint(polresultant(f1(x), g1(x)))
%15 = 
[3 6]

[19 3]

[163 1]

? f2(x) = (((x^5-1)/(x-1))^5-5^5) / (x^4 + x^3 + x^2 + x + 1 - 5)
? g2(x) = (x^25-1)/(x^5-1)
? factorint(polresultant(f2(x), g2(x)))
%16 = 
[5 16]

[151 1]

[701 1]

[2551 1]

[24251 1]

[34651 1]

[144853351 1]

[659575601 1]

[1271785993801 1]
The next two polynomials have a common factor (is this intended?)

Code:
? f3(x) = (x^2+x+1)^3-3^3
? g3(x) = (x^162+x^81+1)^3-3^3
? gcd(f3(x), g3(x))
%23 = x - 1
? polresultant(f3(x)/(x-1),g3(x)/(x-1))
<big highly composite number, has your c162 as divisor>
The next two are coprime
Code:
? f4(x)=((x^2+x+1)^9-3^9)/((x^2+x+1)^3-3^3)
? g4(x)=x^162 + x^81 + 1
? polresultant(f4(x),g4(x))
<big highly composite number, has your c165 as divisor>
I wonder if we can use the fact that the number to factor divides the resultant of the two polynomials to make SNFS polynomials. Then the factorization would be quite simple, if ECM should fail. If not, both could still be factored with GNFS, although with much more effort.

Alex
akruppa is offline   Reply With Quote
Old 2009-05-04, 17:52   #9
mklasson
 
Feb 2004

2·3·43 Posts
Default

sigma(62060021^18):

********** Factor found in step 2: 2859153813495302135105360393
Found probable prime factor of 28 digits: 2859153813495302135105360393
Probable prime cofactor 65219432427202213218611042380245134951516556220905814475152737256300473009279433432471898046319778085284772450023 has 113 digits
mklasson is offline   Reply With Quote
Old 2009-05-04, 17:52   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

9A316 Posts
Default

Quote:
Originally Posted by 10metreh View Post
Sorry if I was making a mistake, but I was simply diving out the factor x - 1 from x^7 - 1 to get the polynomial x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 with root 172827552198815888791.

(Yes, you are more experienced than me, so you are giving me advice if you correct me.)
Sorry, I made a mistake, too: I meant the first number, where you start with the 13th cyclotomic polynomial. My apologies.

I thought your telling Joseph off ("I suggest you factor them yourself.") wasn't called for.

Alex
akruppa is offline   Reply With Quote
Old 2009-05-04, 18:04   #11
10metreh
 
10metreh's Avatar
 
Nov 2008

232210 Posts
Default

Quote:
Originally Posted by akruppa View Post
Sorry, I made a mistake, too: I meant the first number, where you start with the 13th cyclotomic polynomial. My apologies.

I thought your telling Joseph off ("I suggest you factor them yourself.") wasn't called for.

Alex
Actually I wasn't meaning to tell him off. I was just informing him that there were easy numbers in that group. (I did not say "I order you to factor them yourself".)

Anyway: I managed to get the polynomials x^6 + x^5 - 5x^4 - 4x^3 + 6x^2 + 3x - 1 and -10177286401x + 103577158487979532802 using phi (yes, I know that is your program). I presume the method used is similar to the one mentioned on the wiki for x^13k-1.

Last fiddled with by 10metreh on 2009-05-04 at 18:15
10metreh is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odd perfect related road blocks jchein1 Factoring 31 2009-04-29 15:18
Odd perfect related number Zeta-Flux Factoring 46 2009-04-24 22:03
Question about triming [code] blocks schickel Forum Feedback 4 2009-04-01 03:27
MonoDevelop vs. Code::Blocks ixfd64 Software 1 2008-03-10 08:30
Intels Intresting Road moo Hardware 7 2005-12-13 02:20

All times are UTC. The time now is 10:20.

Sat Jan 23 10:20:02 UTC 2021 up 51 days, 6:31, 0 users, load averages: 1.78, 1.67, 1.86

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.