mersenneforum.org Can I borrow some ECM of a friendly CPU?
 Register FAQ Search Today's Posts Mark Forums Read

2022-08-29, 06:41   #12
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×3×29×67 Posts

Quote:
 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.

2022-08-29, 07:40   #13
fatphil

May 2003

3×5×17 Posts

Quote:
 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.

2022-08-29, 09:16   #14
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2D8A16 Posts

Quote:
 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]

2022-08-29, 14:08   #15
fatphil

May 2003

25510 Posts

Quote:
 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.

2022-08-29, 14:48   #16
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2D8A16 Posts

Quote:
 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.

Last fiddled with by xilman on 2022-08-29 at 14:49

2022-08-29, 16:11   #17
fatphil

May 2003

3×5×17 Posts

Quote:
 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.

 2022-08-29, 17:18 #18 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 3·251 Posts I just checked, and your 82177-digit number is Lucas(393216)/2. Therefore, it's divisible by Lucas(131072) Last fiddled with by Stargate38 on 2022-08-29 at 17:20 Reason: forgot to mention which number
2022-08-29, 17:59   #19
fatphil

May 2003

3·5·17 Posts

Quote:
 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?

Last fiddled with by fatphil on 2022-08-29 at 18:00

 2022-08-29, 18:29 #20 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 13618 Posts 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. Last fiddled with by Stargate38 on 2022-08-29 at 18:30
 2022-08-29, 19:07 #21 Dr Sardonicus     Feb 2017 Nowhere 11000010011102 Posts The fundamental unit $\epsilon$ > 1 of the ring of algebraic integers in Q(sqrt(5)) is the "golden ratio" $\frac{1+\sqrt{5}}{2}$. We have $\epsilon^{n}\;=\;\frac{L_{n}\;+\;F_{n}\sqrt{5}}{2}.$ Thus, the Lucas and Fibonacci numbers satisfy $L_{n}^{2}\;-\;5F_{n}^{2}\;=\;4\cdot(-1)^{n}$. Both Ln and Fn are even when n is divisible by 3. The numerators and denominators of the SCF for sqrt(5) (solutions to x2 - 5y2 = ±1) are thus x = (1/2)L3k and y = (1/2)F3k. Now L3k is divisible by Ld for every divisor of 3k whose cofactor is odd, and F3k is divisible by Fd for every divisor d of 3k. You have to be a little careful in translating this to results about (1/2)L3k and (1/2)F3k.
2022-08-29, 19:08   #22
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×3×29×67 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post hansl Math 3 2020-09-02 10:40 Sutton Shin mersennewiki 0 2012-09-29 08:03 davieddy Soap Box 9 2012-07-13 05:39 davieddy Lounge 1 2011-06-10 18:42 Xyzzy Lounge 11 2003-05-15 08:38

All times are UTC. The time now is 15:37.

Thu Feb 2 15:37:16 UTC 2023 up 168 days, 13:05, 1 user, load averages: 0.95, 1.05, 1.02