Gratuitous OPN factors - Page 42

wblipp · 2016-05-04, 14:29

yoyo@home finished the factorization of
P49^5-1 as P41 * P130
P52a^5-1 as P42 * P124
P52b^5-1 as P51 * P120

yoyo@home reduced the unfactored part of P213+1 from C173 to C130

---------------------------

factorization of P55^5-1 finished as P46 * P132

P55 is the largest factor of P37^3-1
P37 is the largest factor of P29^3-1
P29 is the largest factor of 19^43-1

wblipp · 2016-05-07, 19:14

finished or reduced in ECM prep
p53^5-1 as P42 * P141
P50^5-1 as P52 * P107
P55^5-1 as P43 * C156

wblipp · 2016-05-16, 14:31

P52^5-1 finished as P42 * P124
P49^5-1 reduced as P41 * C136

wblipp · 2016-05-31, 02:36

yoyo finished
P50a^5-1 with P51 * P82
P50b^5-1 with P53 * P91
P51^5-1 with P51 * P129

wblipp · 2016-06-04, 05:16

yoyo@home finished
P49^5-1 as P41 * P95
P53^5-1 as P51 * P114

wblipp · 2016-06-16, 03:40

From the t2000 file

P50^5-1 finished as P38 * P137
P54^5-1 finished as P55 * P129
P51^5-1 finished as P36 * P168
P55^5-1 finished as P42 * P176

RichD · 2017-07-13, 18:14

Some good news! First, Ryan finished off the t500 file with the last number 71316922984999^17-1 factored as p87 * p118. A degree halving octic was used by SNFS. 3LP on the algebraic side helped but the process wasn’t as pretty as hoped, but it did get the job done.

Using the traditional method to develop a sextic polynomial, we end up with a tough SNFS difficulty of 249. When we utilize degree halving, it reduces it to an octic SNFS-234 difficulty. Given a sufficiently large base one can benefit from the octic polynomial.

He has completed a couple numbers in this range so a proof of concept has been shown. All the software components can handle a degree-8 polynomial correctly.

lorgix · 2017-10-28, 14:17

I'm working on completely factoring p^q-1 for p and q <10000 where the composite is at most 160 digits. Mostly SNFS recently.
GNFS on 5591^61-1 just finished though.

Code:

p62 = 19854797568116156306635142178732108251384729288830403979568069
p96 = 247633825328175664825512491110977235983869177534796524399915330253077554109821898015967194396563

Y0: -1102225542723473838562347398326
Y1: 46997859610529773
c0: -58978494067576752313653893703695131059
c1: 69333563221774646199876658034895
c2: 169011075619257748542422093
c3: -2025152247490881835
c4: -20641467903774
c5: 3022200
skew: 2469850.25960
rlim: 67108862
alim: 67108862
lpbr: 30
lpba: 30
mfbr: 60
mfba: 60
rlambda: 2.6
alambda: 2.6

sieved over 16500000-50362000 (most of that range anyway)

Wed Oct 25 07:47:30 2017  found 11776749 hash collisions in 83577588 relations
Wed Oct 25 07:47:59 2017  commencing duplicate removal, pass 2
Wed Oct 25 07:48:46 2017  found 10565354 duplicates and 73012234 unique relations
Wed Oct 25 07:48:46 2017  memory use: 394.4 MB
Wed Oct 25 07:48:46 2017  reading ideals above 720000
Wed Oct 25 07:48:47 2017  commencing singleton removal, initial pass
Wed Oct 25 08:00:23 2017  memory use: 1506.0 MB
Wed Oct 25 08:00:24 2017  reading all ideals from disk
Wed Oct 25 08:00:25 2017  memory use: 2673.0 MB
Wed Oct 25 08:00:33 2017  keeping 80042168 ideals with weight <= 200, target excess is 378627
Wed Oct 25 08:00:41 2017  commencing in-memory singleton removal
Wed Oct 25 08:00:47 2017  begin with 73012234 relations and 80042168 unique ideals
Wed Oct 25 08:02:01 2017  reduce to 27792679 relations and 27264338 ideals in 24 passes
Wed Oct 25 08:02:01 2017  max relations containing the same ideal: 110
Wed Oct 25 08:02:15 2017  removing 900034 relations and 855467 ideals in 44567 cliques
Wed Oct 25 08:02:16 2017  commencing in-memory singleton removal
Wed Oct 25 08:02:18 2017  begin with 26892645 relations and 27264338 unique ideals
Wed Oct 25 08:02:44 2017  reduce to 26865333 relations and 26381473 ideals in 10 passes
Wed Oct 25 08:02:44 2017  max relations containing the same ideal: 109
Wed Oct 25 08:02:56 2017  removing 644751 relations and 600184 ideals in 44567 cliques
Wed Oct 25 08:02:57 2017  commencing in-memory singleton removal
Wed Oct 25 08:02:59 2017  begin with 26220582 relations and 26381473 unique ideals
Wed Oct 25 08:03:23 2017  reduce to 26206209 relations and 25766881 ideals in 10 passes
Wed Oct 25 08:03:23 2017  max relations containing the same ideal: 107
Wed Oct 25 08:03:39 2017  relations with 0 large ideals: 1231
Wed Oct 25 08:03:39 2017  relations with 1 large ideals: 4655
Wed Oct 25 08:03:39 2017  relations with 2 large ideals: 70881
Wed Oct 25 08:03:39 2017  relations with 3 large ideals: 529558
Wed Oct 25 08:03:39 2017  relations with 4 large ideals: 2155104
Wed Oct 25 08:03:39 2017  relations with 5 large ideals: 5142552
Wed Oct 25 08:03:39 2017  relations with 6 large ideals: 7424502
Wed Oct 25 08:03:39 2017  relations with 7+ large ideals: 10877726
Wed Oct 25 08:03:39 2017  commencing 2-way merge
Wed Oct 25 08:03:58 2017  reduce to 14672195 relation sets and 14232907 unique ideals
Wed Oct 25 08:03:58 2017  ignored 40 oversize relation sets
Wed Oct 25 08:03:58 2017  commencing full merge
Wed Oct 25 08:07:48 2017  memory use: 1610.3 MB
Wed Oct 25 08:07:50 2017  found 7678071 cycles, need 7643107
Wed Oct 25 08:07:50 2017  weight of 7643107 cycles is about 535310473 (70.04/cycle)
Wed Oct 25 08:07:50 2017  distribution of cycle lengths:
Wed Oct 25 08:07:50 2017  1 relations: 1249475
Wed Oct 25 08:07:50 2017  2 relations: 1100206
Wed Oct 25 08:07:50 2017  3 relations: 995357
Wed Oct 25 08:07:50 2017  4 relations: 828525
Wed Oct 25 08:07:50 2017  5 relations: 690754
Wed Oct 25 08:07:50 2017  6 relations: 560600
Wed Oct 25 08:07:50 2017  7 relations: 446224
Wed Oct 25 08:07:50 2017  8 relations: 354350
Wed Oct 25 08:07:50 2017  9 relations: 281155
Wed Oct 25 08:07:50 2017  10+ relations: 1136461
Wed Oct 25 08:07:50 2017  heaviest cycle: 28 relations
Wed Oct 25 08:07:52 2017  commencing cycle optimization
Wed Oct 25 08:08:02 2017  start with 40798309 relations
Wed Oct 25 08:09:01 2017  pruned 662405 relations
Wed Oct 25 08:09:01 2017  memory use: 1458.4 MB
Wed Oct 25 08:09:01 2017  distribution of cycle lengths:
Wed Oct 25 08:09:01 2017  1 relations: 1249475
Wed Oct 25 08:09:01 2017  2 relations: 1121423
Wed Oct 25 08:09:01 2017  3 relations: 1023038
Wed Oct 25 08:09:01 2017  4 relations: 837460
Wed Oct 25 08:09:01 2017  5 relations: 696357
Wed Oct 25 08:09:01 2017  6 relations: 558353
Wed Oct 25 08:09:01 2017  7 relations: 442014
Wed Oct 25 08:09:01 2017  8 relations: 348205
Wed Oct 25 08:09:01 2017  9 relations: 275093
Wed Oct 25 08:09:01 2017  10+ relations: 1091689
Wed Oct 25 08:09:01 2017  heaviest cycle: 28 relations
Wed Oct 25 08:09:09 2017  RelProcTime: 1892
Wed Oct 25 08:09:09 2017  
Wed Oct 25 08:09:09 2017  commencing linear algebra
Wed Oct 25 08:09:11 2017  read 7643107 cycles
Wed Oct 25 08:09:23 2017  cycles contain 25491735 unique relations
Wed Oct 25 08:12:25 2017  read 25491735 relations
Wed Oct 25 08:12:57 2017  using 20 quadratic characters above 1073741102
Wed Oct 25 08:14:34 2017  building initial matrix
Wed Oct 25 08:18:11 2017  memory use: 3374.1 MB
Wed Oct 25 08:18:16 2017  read 7643107 cycles
Wed Oct 25 08:18:17 2017  matrix is 7642920 x 7643107 (2348.3 MB) with weight 728033563 (95.25/col)
Wed Oct 25 08:18:17 2017  sparse part has weight 523884650 (68.54/col)
Wed Oct 25 08:19:32 2017  filtering completed in 2 passes
Wed Oct 25 08:19:34 2017  matrix is 7624534 x 7624722 (2346.7 MB) with weight 727282392 (95.38/col)
Wed Oct 25 08:19:34 2017  sparse part has weight 523667146 (68.68/col)
Wed Oct 25 08:19:50 2017  matrix starts at (0, 0)
Wed Oct 25 08:19:52 2017  matrix is 7624534 x 7624722 (2346.7 MB) with weight 727282392 (95.38/col)
Wed Oct 25 08:19:52 2017  sparse part has weight 523667146 (68.68/col)
Wed Oct 25 08:19:52 2017  saving the first 48 matrix rows for later
Wed Oct 25 08:19:53 2017  matrix includes 64 packed rows
Wed Oct 25 08:19:55 2017  matrix is 7624486 x 7624722 (2270.5 MB) with weight 584996764 (76.72/col)
Wed Oct 25 08:19:55 2017  sparse part has weight 518945808 (68.06/col)

RichD · 2018-02-24, 05:21

One of yoyo's workers found a p57 at B1=43e6.
Remaining composite of 1583330397709302767840785182434201286717675016979587310473^5-1

Code:

GMP-ECM 7.0.5-dev [configured with GMP 6.1.2, --enable-asm-redc] [ECM]
Input number is 2106340910946119324794956566167621294668452914326701941707184578373972769308726034798720971612989447924990406447082496794304554453917648558922028756885918964474504581500135261648254381412813049433339215569731319126421101 (220 digits)
Using B1=43000000, B2=240490660426, polynomial Dickson(12), sigma=0:4388281831402397563
Step 1 took 272218ms
Step 2 took 58953ms
********** Factor found in step 2: 223946205042911562949074601439141113968259630994577798421
Found prime factor of 57 digits: 223946205042911562949074601439141113968259630994577798421
Prime cofactor 9405566441916315430980225700044655594470473943916582652572100070562933370103936040265155535673726838838590120361219574083639862607576029303448626273558834559769081 has 163 digits

RichD · 2019-05-29, 20:25

The remaining composite of 18911620022703649170272947821393946139719752883^5-1 has the following factors:

Code:

p91: 1951509081860151950726196208254975772331029783659632662350257697740285656167748087020778481
p91: 4006217391488938639099562726444252165545913372849342474762249190539554128074495108476277441

ThomRuley · 2019-05-29, 21:08

Quote:

Originally Posted by RichD

Some good news! First, Ryan finished off the t500 file with the last number 71316922984999^17-1 factored as p87 * p118. A degree halving octic was used by SNFS. 3LP on the algebraic side helped but the process wasn’t as pretty as hoped, but it did get the job done.

Using the traditional method to develop a sextic polynomial, we end up with a tough SNFS difficulty of 249. When we utilize degree halving, it reduces it to an octic SNFS-234 difficulty. Given a sufficiently large base one can benefit from the octic polynomial.

He has completed a couple numbers in this range so a proof of concept has been shown. All the software components can handle a degree-8 polynomial correctly.

Does that mean all the composites are done in Pascal's t500?

2017-07-13, 18:14	#458
RichD Sep 2008 Kansas D40₁₆ Posts	t500 File Completed Some good news! First, Ryan finished off the t500 file with the last number 71316922984999^17-1 factored as p87 * p118. A degree halving octic was used by SNFS. 3LP on the algebraic side helped but the process wasn’t as pretty as hoped, but it did get the job done. Using the traditional method to develop a sextic polynomial, we end up with a tough SNFS difficulty of 249. When we utilize degree halving, it reduces it to an octic SNFS-234 difficulty. Given a sufficiently large base one can benefit from the octic polynomial. He has completed a couple numbers in this range so a proof of concept has been shown. All the software components can handle a degree-8 polynomial correctly.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Gratuitous factors thread	fivemack	Factoring	522	2021-08-04 20:35
Known factors	ATH	PrimeNet	2	2014-09-04 19:45
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
JasonG's gratuitous C++ thread	jasong	Programming	16	2006-11-07 01:03
Gratuitous hardware-related banana thread	GP2	Hardware	7	2003-11-24 06:13

2016-05-04, 14:29	#452
wblipp "William" May 2003 New Haven 2×7×13² Posts	yoyo@home finished the factorization of P49^5-1 as P41 * P130 P52a^5-1 as P42 * P124 P52b^5-1 as P51 * P120 yoyo@home reduced the unfactored part of P213+1 from C173 to C130 --------------------------- factorization of P55^5-1 finished as P46 * P132 P55 is the largest factor of P37^3-1 P37 is the largest factor of P29^3-1 P29 is the largest factor of 19^43-1

2016-05-07, 19:14	#453
wblipp "William" May 2003 New Haven 2·7·13² Posts	finished or reduced in ECM prep p53^5-1 as P42 * P141 P50^5-1 as P52 * P107 P55^5-1 as P43 * C156

2016-05-16, 14:31	#454
wblipp "William" May 2003 New Haven 2×7×13² Posts	P52^5-1 finished as P42 * P124 P49^5-1 reduced as P41 * C136

2016-05-31, 02:36	#455
wblipp "William" May 2003 New Haven 100100111110₂ Posts	yoyo finished P50a^5-1 with P51 * P82 P50b^5-1 with P53 * P91 P51^5-1 with P51 * P129

2016-06-04, 05:16	#456
wblipp "William" May 2003 New Haven 2366₁₀ Posts	yoyo@home finished P49^5-1 as P41 * P95 P53^5-1 as P51 * P114

2016-06-16, 03:40	#457
wblipp "William" May 2003 New Haven 2·7·13² Posts	From the t2000 file P50^5-1 finished as P38 * P137 P54^5-1 finished as P55 * P129 P51^5-1 finished as P36 * P168 P55^5-1 finished as P42 * P176

2019-05-29, 20:25	#461
RichD Sep 2008 Kansas 2⁶·53 Posts	The remaining composite of 18911620022703649170272947821393946139719752883^5-1 has the following factors: Code: p91: 1951509081860151950726196208254975772331029783659632662350257697740285656167748087020778481 p91: 4006217391488938639099562726444252165545913372849342474762249190539554128074495108476277441