Can I borrow some ECM of a friendly CPU?

[xilman]

Originally Posted by fatphil

Just updated with some info about the direction I headed in, so you don't need to reinvent the wheel. It looks like I may have to reinvent some of my factors, as I can't find the window I was working in!

But tonight is sauna night, so I'm happily tucked away there for the rest of the evening.

pcl@nut:~/Desktop$ ecm -maxmem 2048 1000000 < composites.txt
GMP-ECM 7.0.4 [configured with GMP 6.2.1, --enable-asm-redc] [ECM]
Input number is 9614319269...4094423041 (82177 digits)
Using B1=1000000, B2=914058610, polynomial Dickson(3), sigma=0:4416831086328320100
Step 1 took 27856254ms
Step 2 took 7836917ms
********** Factor found in step 2: 2749553154323378809339903
Found prime factor of 25 digits: 2749553154323378809339903
Composite cofactor 3496...9247 has 82153 digits

The above has been lightly edited. Note it was found on the first curve tried.

[fatphil]

Originally Posted by xilman

Step 1 took 27856254ms
Step 2 took 7836917ms
Found prime factor of 25 digits: 2749553154323378809339903

Wow - thanks! Gmp-ecm never stops impressing me. I'm beginning to regret my strategy of starting with a small B1, I'm still on my 174th failing curve with B1 up to 35000...
I don't think I'll bother with the 160kdigit next term, it's probably time to look more closely at the algebra.

[xilman]

Originally Posted by fatphil

I didn't do P+/-1 because I was prepared to just let ECM run, and with 100 curves, now 125, the Hasse coverage should have pulled out something that was in range of P+/-1.

FWIW

? factor(2749553154323378809339902)
%1 =
[ 2 1]

[ 3 1]

[ 232357 1]

[ 423601 1]

[4655840911681 1]

? factor(2749553154323378809339904)
%2 =
[ 2 18]

[ 313 1]

[ 113083 1]

[296333355629 1]

[fatphil]

Originally Posted by xilman

Note it was found on the first curve tried.

It's nice when things drop out just at the ideal moment. For instance, I was just about to give up on this number:

Run 100 out of 100:
Using B1=10315491, B2=10315490-35133066160, polynomial Dickson(12), sigma=1:1661695324
Step 1 took 12909ms
Step 2 took 6496ms
********** Factor found in step 2: 125960894984050328038716298487435392001
Found prime factor of 39 digits: 125960894984050328038716298487435392001
Prime cofactor 260850953670702126641628144218597843056427843281352119936811457220827426196135100642146995717121 has 96 digits

Bosh!

All the known factors in the numerators are now up at http://fatphil.org/maths/sqrt_cf/sqrt5.html

I'll need to read up on the denominators a bit more before deciding if there's anything more to discover.

[xilman]

Originally Posted by fatphil

It's nice when things drop out just at the ideal moment. For instance, I was just about to give up on this number:

Run 100 out of 100:
Using B1=10315491, B2=10315490-35133066160, polynomial Dickson(12), sigma=1:1661695324
Step 1 took 12909ms
Step 2 took 6496ms
********** Factor found in step 2: 125960894984050328038716298487435392001
Found prime factor of 39 digits: 125960894984050328038716298487435392001
Prime cofactor 260850953670702126641628144218597843056427843281352119936811457220827426196135100642146995717121 has 96 digits

Bosh!

All the known factors in the numerators are now up at http://fatphil.org/maths/sqrt_cf/sqrt5.html

]I am prepared to spend a day or two on your 160K-digit composite if you think it worthwhile.

You should have switched to GNFS for the C135 IMO.

[fatphil]

Originally Posted by xilman

]I am prepared to spend a day or two on your 160K-digit composite if you think it worthwhile.

You should have switched to GNFS for the C135 IMO.

Now I've worked out the algebraic structure, these are just a^n+b^n and a^n-b^n sequences. I don't think there's any need to hunt for factors any more, at least on the numerator side, but I'll continue to fill out a decent sized table of factors on the denominator side, mostly for schitzengiggles. A deeper hunt for PRPs on the denominator side should be done still.

[Stargate38]

I just checked, and your 82177-digit number is Lucas(393216)/2. Therefore, it's divisible by Lucas(131072)

[fatphil]

Originally Posted by Stargate38

I just checked, and your 82177-digit number is Lucas(393216)/2. Therefore, it's divisible by Lucas(131072)

In that case all of them will be divisible by smaller Lucas numbers, and therefore none can be prime.

Congrats, you've solved the first half of the conjecture!

Edit: how did you work out it was half-a-lucas?

[Stargate38]

I copy-pasted the full number into FactorDB. After hitting "Factorize", I then clicked on the link under where it says "number". Since the number was already on the DB, it simplified it to the shortest known formula.

[Dr Sardonicus]

The fundamental unit > 1 of the ring of algebraic integers in Q(sqrt(5)) is the "golden ratio" .

We have

Thus, the Lucas and Fibonacci numbers satisfy .

Both L_n and F_n are even when n is divisible by 3. The numerators and denominators of the SCF for sqrt(5) (solutions to x² - 5y² = ±1) are thus x = (1/2)L_3k and y = (1/2)F_3k.

Now L_3k is divisible by L_d for every divisor of 3k whose cofactor is odd, and F_3k is divisible by F_d for every divisor d of 3k.

You have to be a little careful in translating this to results about (1/2)L_3k and (1/2)F_3k.

[xilman]

Originally Posted by fatphil

Now I've worked out the algebraic structure, these are just a^n+b^n and a^n-b^n sequences. I don't think there's any need to hunt for factors any more, at least on the numerator side, but I'll continue to fill out a decent sized table of factors on the denominator side, mostly for schitzengiggles. A deeper hunt for PRPs on the denominator side should be done still.

Let me know how (if) I can help.