[QUOTE=Andi47;98524]A few ECM curves at the 45 digit level did the trick:

Run 57 out of 1000:
Using B1=11000000, B2=35133391030, polynomial Dickson(12), sigma=2448571626
Step 1 took 100328ms
Step 2 took 54516ms
********** Factor found in step 2: 1076768463221541221588996172658220297179427
Found probable prime factor of 43 digits: 1076768463221541221588996172658220297179427
Probable prime cofactor 3937302371596518955301979501006666039072382909280067817582200677 has 64 digits

Edit: Both factors are prime - (with Primo)[/QUOTE]



Nice! A lot faster than either GNFS or SNFS....

[QUOTE=R.D. Silverman;98527]Nice! A lot faster than either GNFS or SNFS....[/QUOTE]

Confirmed.

prp43 factor: 1076768463221541221588996172658220297179427
prp64 factor: 3937302371596518955301979501006666039072382909280067817582200677

:rolleyes:

Luigi

[QUOTE=ET_;98586]Confirmed.

prp43 factor: 1076768463221541221588996172658220297179427
prp64 factor: 3937302371596518955301979501006666039072382909280067817582200677

:rolleyes:

Luigi[/QUOTE]

if Primo certifies a number as prime, is it 100.0000000% sure that it is prime, or is there still a small chance that it will be not prime? (I have checked both, the 43 digit factor and the 64 digit cofactor with Primo.)

4,3,302+
 

You really made quick work of that p43 factor via ECM.

For 4,3,302+, the C181 = p44.p138, where:

[CODE]p44 = 20695547811498020793670568184883348218563381
p138 = 128321800817873917759392375361867607670314329269986496653069534540871571320466666897883324576957991424252956187579729363809084825366199421[/CODE]

I'm going after 4,3,337+ using gnfs, and hitting the remaining composites in the 4-3 and 4+3 tables with lots of ECM curves.

5,4,229-
 

[QUOTE=FactorEyes;98711]You really made quick work of that p43 factor via ECM.

For 4,3,302+, the C181 = p44.p138, where:

[CODE]p44 = 20695547811498020793670568184883348218563381
p138 = 128321800817873917759392375361867607670314329269986496653069534540871571320466666897883324576957991424252956187579729363809084825366199421[/CODE]

I'm going after 4,3,337+ using gnfs, and hitting the remaining composites in the 4-3 and 4+3 tables with lots of ECM curves.[/QUOTE]

Another ECM miss:

5,4,229- C161 = p40.p47.p75

Calling this an ECM miss might be misplaced. Even if the p40 were
found, the number would still probably need to be finished by another method.

1359779321416264105271906309592600166361.
45834215065697095094552317796450541256757090711.
185982791640271170394013102224495851072001206804623787532442011434922376011

5,4,233+ is in progress. 5,3,232+ will follow.

What have I screwed up this time?
 

I'm trying to do 5^267+3^267.

[code]type: snfs
n: 9631277431970100278263127220673756672789691637793100395927082111961268437428170159670658864071393774113579941806311
m: 468090866484631844163850197698427225391228780546631780400019368968350027366022665778235516301831100500208449420866
c5: 25
c0: 9
y1: 19383245667680019896796723
y0: -11102230246251565404236316680908203125
skew: 1 [/code]

I've confirmed with magma that 25m^5+9 and y1m+y0 are both congruent to 0 mod n, but factLat.pl tells me that the snfs difficulty is about 570, where I was expecting 187, and the siever unsurprisingly gives me no relations at all. What have I done wrong?

(my reasoning: m is (5/3)^53 mod n; (3^53)*m-5^53=0. 5^267+3^267 = 0 mod n, so 5^2 * (5^53)^5 + 3^2 * (3^53)^5 = 0 mod n, so divide through by 3^53 and get 5^2 * m + 3^2 = 0 mod n)

[QUOTE=fivemack;98771]I'm trying to do 5^267+3^267.

[code]type: snfs
n: 9631277431970100278263127220673756672789691637793100395927082111961268437428170159670658864071393774113579941806311
m: 468090866484631844163850197698427225391228780546631780400019368968350027366022665778235516301831100500208449420866
c5: 25
c0: 9
y1: 19383245667680019896796723
y0: -11102230246251565404236316680908203125
skew: 1 [/code]

I've confirmed with magma that 25m^5+9 and y1m+y0 are both congruent to 0 mod n, but factLat.pl tells me that the snfs difficulty is about 570, where I was expecting 187, and the siever unsurprisingly gives me no relations at all. What have I done wrong?

(my reasoning: m is (5/3)^53 mod n; (3^53)*m-5^53=0. 5^267+3^267 = 0 mod n, so 5^2 * (5^53)^5 + 3^2 * (3^53)^5 = 0 mod n, so divide through by 3^53 and get 5^2 * m + 3^2 = 0 mod n)[/QUOTE]

Your c5, c0, y1, & y0 look good. But your n should really be the whole thing, 5^267+3^267, with m computed mod this n:

[CODE]n:4216879177292209289739429620508007603083984552947403020031129834973570970445878947688560576310691010152031411883351189248053570757790931706337896390916981128575229467974311073438353066712

m:3057108016359105925308755696122704212889873115288936308284755319929051725226717059888777911845533384949625767165429498621589844090261221171084443758878945432692076931784661984357408124367[/CODE]

I'd include the line

KNOWNDIV=5794081232162

in your .poly file for ggnfs, so that it knows to avoid the divisors 2, 19, 1069, 2671, 53401 when performing inversions mod n, or doing something with the factor base -- I can't remember. I can't figure out why ggnfs needs to be spoon-fed this information, since it's not difficult to compute.

This gives snfs difficulty of 186.6249911577170208779317151085603618529 (those last 30 decimal places are critical!). Should finish faster than SNFS difficulty 570.

[QUOTE=fivemack;98771]I'm trying to do 5^267+3^267.

[code]type: snfs
n: 9631277431970100278263127220673756672789691637793100395927082111961268437428170159670658864071393774113579941806311
m: 468090866484631844163850197698427225391228780546631780400019368968350027366022665778235516301831100500208449420866
c5: 25
c0: 9
y1: 19383245667680019896796723
y0: -11102230246251565404236316680908203125
skew: 1 [/code]

I've confirmed with magma that 25m^5+9 and y1m+y0 are both congruent to 0 mod n, but factLat.pl tells me that the snfs difficulty is about 570, where I was expecting 187, and the siever unsurprisingly gives me no relations at all. What have I done wrong?

(my reasoning: m is (5/3)^53 mod n; (3^53)*m-5^53=0. 5^267+3^267 = 0 mod n, so 5^2 * (5^53)^5 + 3^2 * (3^53)^5 = 0 mod n, so divide through by 3^53 and get 5^2 * m + 3^2 = 0 mod n)[/QUOTE]

No! No! No!

Your exponent is divisible by 3! Use the know algebraic factorization!
=====> Use a quartic polynomial with (5/3)^45 as the root.
This is a *trivial* SNFS factorization.

N = 5^267 + 3^267. Put 3^-267N = [(5/3)^89]^3 + 1. Factor
out (5/3)^89 + 1, Giving (5/3)^178 - (5/3)^89 + 1. Multiply by (5/3)^2
Giving (5/3)^180 - (5/3) * (5/3)^90 + (5/3)^2. Now clear the
denominators to get x^4 - 15 x^2 + 25 with x = (5/3)^45.

This is difficulty around 125!!!! It is trivial.

[QUOTE=R.D. Silverman;98814]No! No! No!

Your exponent is divisible by 3! Use the know algebraic factorization!
=====> Use a quartic polynomial with (5/3)^45 as the root.
This is a *trivial* SNFS factorization.

N = 5^267 + 3^267. Put 3^-267N = [(5/3)^89]^3 + 1. Factor
out (5/3)^89 + 1, Giving (5/3)^178 - (5/3)^89 + 1. Multiply by (5/3)^2
Giving (5/3)^180 - (5/3) * (5/3)^90 + (5/3)^2. Now clear the
denominators to get x^4 - 15 x^2 + 25 with x = (5/3)^45.

This is difficulty around 125!!!! It is trivial.[/QUOTE]

Oops. Typo. It should be 9x^4

I need a new brain ... didn't notice that 267 was composite.

I think the root of my problems was that the ggnfs script requires the linear terms to be called Y1 and Y0, not y1 and y0, so was calculating the difficulty as f(m) over Z which is of course enormous.

I now get really weird messages (six 'warning: not enough polynomials in mpqs with N', each printed twice, and a final
[code]
warning: not enough polynomials in mpqs with 22908471599987
dec.2
2072 -23384578 2231424595 -> Return value 256. Updating job file and terminating...
[/code]
but this looks like a PowerPC-specific bug, the job starts fine on my P4/Linux machine and should be done by the morning.

Another weird problem
 

The sieving for 5^267+3^267 completed overnight, as you'd expect; twelve dependencies all failed to produce a factorisation other than 1*N. I tried a bit more sieving and rebuilding the matrix, but the sqrt step still failed.

It turns out that 9*x^4 + 15*x^2 + 25 is one of those polynomials that is irreducible over Z but splits modulo every prime. I suspect this is problematic for the way that ggnfs uses to compute square roots :sad:

Any more ideas?