Gratuitous factors thread - Page 2

FactorEyes · 2008-03-20, 00:29

Way back, working on 4^307+3^307. Only 1992 ECM curves at 3E6:

Code:

p47 = 14718260945227321993538833517239503165838463191

One word: gift

Seems as if everyone enjoys splitting a composite into two primes of similar magnitude. A p60.p90 is just as good as a p72.p78, but there is something prettier about the latter.

FactorEyes · 2008-04-20, 05:31

5^292 + 4^292 has p50 factor 93172475798334091708528467222762440891545544410081. Personal best as far as SNFS magnitude goes, at 205 digits. 200 digits ain't what it used to be.

Also, my first 3-fold split on an SNFS:

11^187 - 3^187: c154 = p47.p51.p57
p47: 92534718300915679831411055777591569981607096953
p51: 180166869627938348894812913800373604941787732024067
p57: 440853492502687501432544008137866572998304338991768202689

Gratuitous? You bet.

bsquared · 2008-04-21, 12:32

Quote:

Originally Posted by FactorEyes

Way back, working on 4^307+3^307. Only 1992 ECM curves at 3E6:

Code:

p47 = 14718260945227321993538833517239503165838463191

One word: gift

Along those lines... a while back working on odd perfect number composites: 33rd curve at 3e6, found a p50:

Code:

 
p50 = 65979282303804033736710199516519274949640336359553

my first and only 50 digit ecm hit so far, and it came ridiculously early.

Andi47 · 2008-04-21, 12:50

Quote:

Originally Posted by bsquared

Along those lines... a while back working on odd perfect number composites: 33rd curve at 3e6, found a p50:

Code:

 
p50 = 65979282303804033736710199516519274949640336359553

my first and only 50 digit ecm hit so far, and it came ridiculously early.

My most lucky punch was a p39 in Feb. 2008, found with the first(!) curve at B1=3e6, step 1:

(from hp925, step 84)

Code:

GMP-ECM 6.1.3 [powered by GMP 4.2.2] [ECM]
Input number is 650576944675485979158248547237813070854356361040731543477683852267812333590882664750245192794302744609158946141500102167987396091343924283140710789700381 (153 digits)
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=468825063
Step 1 took 16454ms
********** Factor found in step 1: 546964903436902596245244724937998114463
Found probable prime factor of 39 digits: 546964903436902596245244724937998114463
Composite cofactor 1189430876803114625123780452913858718532798357398992380994476391429080412306589324674244054137888989886581304686787 has 115 digits

P.S.: The composite cofactor is already factored.

bsquared · 2008-05-01, 03:01

Just finished my largest SNFS to date: 12^163 - 11^163

C176, difficulty 176.

Isn't it nice when there are no wasted factors in SNFS jobs :)

Code:

Wed Apr 30 18:33:37 2008 Msieve v. 1.32
Wed Apr 30 18:33:37 2008 random seeds: 0f9bbe40 a72a3a5a
Wed Apr 30 18:33:37 2008 factoring 80638567651605134105801341144295703524688610355698302434289991680094789293158377759055342137656314689398379368412370811546059861224314747399102796095874850337752864376275025997 (176 digits)
Wed Apr 30 18:33:39 2008 searching for 15-digit factors
Wed Apr 30 18:33:41 2008 commencing number field sieve (176-digit input)
Wed Apr 30 18:33:41 2008 R0: -410186270246002225336426103593500672
Wed Apr 30 18:33:41 2008 R1: 23225154419887808141001767796309131
Wed Apr 30 18:33:41 2008 A0: -144
Wed Apr 30 18:33:41 2008 A1: 0
Wed Apr 30 18:33:41 2008 A2: 0
Wed Apr 30 18:33:41 2008 A3: 0
Wed Apr 30 18:33:41 2008 A4: 0
Wed Apr 30 18:33:41 2008 A5: 121
Wed Apr 30 18:33:41 2008 size score = 1.380090e-012, Murphy alpha = 0.611155, combined = 1.125728e-012
Wed Apr 30 18:34:01 2008 restarting with 9580213 relations
Wed Apr 30 18:34:01 2008 
Wed Apr 30 18:34:01 2008 commencing relation filtering
Wed Apr 30 18:34:01 2008 commencing duplicate removal, pass 1
Wed Apr 30 18:35:26 2008 found 858406 hash collisions in 9580213 relations
Wed Apr 30 18:35:26 2008 commencing duplicate removal, pass 2
Wed Apr 30 18:36:10 2008 found 713339 duplicates and 8866874 unique relations
Wed Apr 30 18:36:10 2008 memory use: 50.6 MB
Wed Apr 30 18:36:11 2008 ignoring smallest 395203 rational and 395015 algebraic ideals
Wed Apr 30 18:36:11 2008 filtering ideals above 5724694
Wed Apr 30 18:36:11 2008 need 1343370 more relations than ideals
Wed Apr 30 18:36:11 2008 commencing singleton removal, pass 1
Wed Apr 30 18:37:30 2008 relations with 0 large ideals: 19713
Wed Apr 30 18:37:30 2008 relations with 1 large ideals: 153993
Wed Apr 30 18:37:30 2008 relations with 2 large ideals: 1122054
Wed Apr 30 18:37:30 2008 relations with 3 large ideals: 2848021
Wed Apr 30 18:37:30 2008 relations with 4 large ideals: 2997837
Wed Apr 30 18:37:30 2008 relations with 5 large ideals: 1401728
Wed Apr 30 18:37:30 2008 relations with 6 large ideals: 292605
Wed Apr 30 18:37:30 2008 relations with 7+ large ideals: 30923
Wed Apr 30 18:37:30 2008 8866874 relations and about 8123394 large ideals
Wed Apr 30 18:37:31 2008 commencing singleton removal, pass 2
Wed Apr 30 18:38:52 2008 found 3558693 singletons
Wed Apr 30 18:38:52 2008 current dataset: 5308181 relations and about 4081278 large ideals
Wed Apr 30 18:38:52 2008 commencing singleton removal, pass 3
Wed Apr 30 18:39:47 2008 found 565853 singletons
Wed Apr 30 18:39:47 2008 current dataset: 4742328 relations and about 3493865 large ideals
Wed Apr 30 18:39:47 2008 commencing singleton removal, pass 4
Wed Apr 30 18:40:38 2008 found 118348 singletons
Wed Apr 30 18:40:38 2008 current dataset: 4623980 relations and about 3374392 large ideals
Wed Apr 30 18:40:38 2008 commencing singleton removal, final pass
Wed Apr 30 18:42:07 2008 memory use: 176.9 MB
Wed Apr 30 18:42:07 2008 commencing in-memory singleton removal
Wed Apr 30 18:42:07 2008 begin with 4623980 relations and 3554647 unique ideals
Wed Apr 30 18:42:11 2008 reduce to 4281327 relations and 3207505 ideals in 10 passes
Wed Apr 30 18:42:11 2008 max relations containing the same ideal: 44
Wed Apr 30 18:42:12 2008 dataset has 35.9% excess relations
Wed Apr 30 18:42:13 2008 ignoring smallest 358343 rational and 358057 algebraic ideals
Wed Apr 30 18:42:13 2008 filtering ideals above 5152224
Wed Apr 30 18:42:13 2008 need 966439 more relations than ideals
Wed Apr 30 18:42:13 2008 commencing singleton removal, final pass
Wed Apr 30 18:43:05 2008 memory use: 176.9 MB
Wed Apr 30 18:43:05 2008 commencing in-memory singleton removal
Wed Apr 30 18:43:05 2008 begin with 4623980 relations and 3628453 unique ideals
Wed Apr 30 18:43:10 2008 reduce to 4281008 relations and 3280982 ideals in 10 passes
Wed Apr 30 18:43:10 2008 max relations containing the same ideal: 44
Wed Apr 30 18:43:12 2008 removing 139153 relations and 122360 ideals in 16793 cliques
Wed Apr 30 18:43:12 2008 commencing in-memory singleton removal
Wed Apr 30 18:43:12 2008 begin with 4141855 relations and 3280982 unique ideals
Wed Apr 30 18:43:15 2008 reduce to 4139759 relations and 3156511 ideals in 6 passes
Wed Apr 30 18:43:15 2008 max relations containing the same ideal: 43
Wed Apr 30 18:43:17 2008 removing 105818 relations and 89025 ideals in 16793 cliques
Wed Apr 30 18:43:17 2008 commencing in-memory singleton removal
Wed Apr 30 18:43:18 2008 begin with 4033941 relations and 3156511 unique ideals
Wed Apr 30 18:43:20 2008 reduce to 4032602 relations and 3066137 ideals in 5 passes
Wed Apr 30 18:43:20 2008 max relations containing the same ideal: 42
Wed Apr 30 18:43:22 2008 dataset has 22.3% excess relations
Wed Apr 30 18:43:23 2008 ignoring smallest 321126 rational and 320784 algebraic ideals
Wed Apr 30 18:43:23 2008 filtering ideals above 4579755
Wed Apr 30 18:43:23 2008 need 853435 more relations than ideals
Wed Apr 30 18:43:23 2008 commencing singleton removal, final pass
Wed Apr 30 18:44:10 2008 memory use: 176.9 MB
Wed Apr 30 18:44:10 2008 commencing in-memory singleton removal
Wed Apr 30 18:44:10 2008 begin with 4032602 relations and 3140616 unique ideals
Wed Apr 30 18:44:12 2008 reduce to 4032391 relations and 3140405 ideals in 4 passes
Wed Apr 30 18:44:12 2008 max relations containing the same ideal: 42
Wed Apr 30 18:44:14 2008 removing 107862 relations and 88587 ideals in 19275 cliques
Wed Apr 30 18:44:14 2008 commencing in-memory singleton removal
Wed Apr 30 18:44:14 2008 begin with 3924529 relations and 3140405 unique ideals
Wed Apr 30 18:44:16 2008 reduce to 3923183 relations and 3050467 ideals in 5 passes
Wed Apr 30 18:44:17 2008 max relations containing the same ideal: 41
Wed Apr 30 18:44:19 2008 removing 100018 relations and 80743 ideals in 19275 cliques
Wed Apr 30 18:44:19 2008 commencing in-memory singleton removal
Wed Apr 30 18:44:19 2008 begin with 3823165 relations and 3050467 unique ideals
Wed Apr 30 18:44:21 2008 reduce to 3821719 relations and 2968276 ideals in 4 passes
Wed Apr 30 18:44:21 2008 max relations containing the same ideal: 40
Wed Apr 30 18:44:23 2008 dataset has 8.0% excess relations
Wed Apr 30 18:44:23 2008 relations with 0 large ideals: 15975
Wed Apr 30 18:44:23 2008 relations with 1 large ideals: 97711
Wed Apr 30 18:44:23 2008 relations with 2 large ideals: 531047
Wed Apr 30 18:44:23 2008 relations with 3 large ideals: 1124161
Wed Apr 30 18:44:23 2008 relations with 4 large ideals: 1177621
Wed Apr 30 18:44:23 2008 relations with 5 large ideals: 645289
Wed Apr 30 18:44:23 2008 relations with 6 large ideals: 197638
Wed Apr 30 18:44:23 2008 relations with 7+ large ideals: 32277
Wed Apr 30 18:44:23 2008 commencing 2-way merge
Wed Apr 30 18:44:27 2008 reduce to 2580540 relation sets and 1727097 unique ideals
Wed Apr 30 18:44:27 2008 commencing full merge
Wed Apr 30 18:45:09 2008 found 1318214 cycles, need 1109297
Wed Apr 30 18:45:09 2008 weight of 1109297 cycles is about 72265196 (65.15/cycle)
Wed Apr 30 18:45:09 2008 distribution of cycle lengths:
Wed Apr 30 18:45:09 2008 1 relations: 147858
Wed Apr 30 18:45:09 2008 2 relations: 126177
Wed Apr 30 18:45:09 2008 3 relations: 128724
Wed Apr 30 18:45:09 2008 4 relations: 122790
Wed Apr 30 18:45:09 2008 5 relations: 116458
Wed Apr 30 18:45:09 2008 6 relations: 104451
Wed Apr 30 18:45:09 2008 7 relations: 93102
Wed Apr 30 18:45:09 2008 8 relations: 80795
Wed Apr 30 18:45:09 2008 9 relations: 69549
Wed Apr 30 18:45:09 2008 10+ relations: 119393
Wed Apr 30 18:45:09 2008 heaviest cycle: 14 relations
Wed Apr 30 18:45:10 2008 commencing cycle optimization
Wed Apr 30 18:45:11 2008 start with 5684484 relations
Wed Apr 30 18:45:23 2008 pruned 106871 relations
Wed Apr 30 18:45:23 2008 distribution of cycle lengths:
Wed Apr 30 18:45:23 2008 1 relations: 147858
Wed Apr 30 18:45:23 2008 2 relations: 127848
Wed Apr 30 18:45:23 2008 3 relations: 132107
Wed Apr 30 18:45:23 2008 4 relations: 125542
Wed Apr 30 18:45:23 2008 5 relations: 120051
Wed Apr 30 18:45:23 2008 6 relations: 107210
Wed Apr 30 18:45:23 2008 7 relations: 95119
Wed Apr 30 18:45:23 2008 8 relations: 81592
Wed Apr 30 18:45:23 2008 9 relations: 68643
Wed Apr 30 18:45:23 2008 10+ relations: 103327
Wed Apr 30 18:45:23 2008 heaviest cycle: 14 relations
Wed Apr 30 18:45:28 2008 
Wed Apr 30 18:45:28 2008 commencing linear algebra
Wed Apr 30 18:45:30 2008 read 1109297 cycles
Wed Apr 30 18:45:33 2008 cycles contain 3031409 unique relations
Wed Apr 30 18:47:45 2008 read 3031409 relations
Wed Apr 30 18:47:50 2008 using 32 quadratic characters above 134216912
Wed Apr 30 18:49:11 2008 read 1109297 cycles
Wed Apr 30 18:50:06 2008 matrix is 1108626 x 1109297 with weight 97696276 (avg 88.07/col)
Wed Apr 30 18:50:27 2008 filtering completed in 3 passes
Wed Apr 30 18:50:27 2008 matrix is 1102784 x 1102984 with weight 97251784 (avg 88.17/col)
Wed Apr 30 18:51:04 2008 read 1102984 cycles
Wed Apr 30 18:53:54 2008 matrix is 1102784 x 1102984 with weight 97251784 (avg 88.17/col)
Wed Apr 30 18:53:54 2008 saving the first 48 matrix rows for later
Wed Apr 30 18:53:55 2008 matrix is 1102736 x 1102984 with weight 74094589 (avg 67.18/col)
Wed Apr 30 18:53:55 2008 matrix includes 64 packed rows
Wed Apr 30 18:53:55 2008 using block size 65536 for processor cache size 4096 kB
Wed Apr 30 18:54:01 2008 commencing Lanczos iteration (2 threads)
Wed Apr 30 20:37:56 2008 lanczos halted after 17441 iterations (dim = 1102735)
Wed Apr 30 20:37:59 2008 recovered 50 nontrivial dependencies
Wed Apr 30 20:37:59 2008 
Wed Apr 30 20:37:59 2008 commencing square root phase
Wed Apr 30 20:37:59 2008 reading relations for dependency 1
Wed Apr 30 20:38:01 2008 read 551332 cycles
Wed Apr 30 20:38:02 2008 cycles contain 1849397 unique relations
Wed Apr 30 20:40:27 2008 read 1849397 relations
Wed Apr 30 20:40:39 2008 multiplying 2777790 relations
Wed Apr 30 20:45:52 2008 multiply complete, coefficients have about 84.06 million bits
Wed Apr 30 20:45:53 2008 initial square root is modulo 1080791
Wed Apr 30 20:52:43 2008 reading relations for dependency 2
Wed Apr 30 20:52:45 2008 read 550793 cycles
Wed Apr 30 20:52:46 2008 cycles contain 1847871 unique relations
Wed Apr 30 20:54:28 2008 read 1847871 relations
Wed Apr 30 20:54:39 2008 multiplying 2774172 relations
Wed Apr 30 20:59:53 2008 multiply complete, coefficients have about 83.95 million bits
Wed Apr 30 20:59:54 2008 initial square root is modulo 1062121
Wed Apr 30 21:06:44 2008 reading relations for dependency 3
Wed Apr 30 21:06:46 2008 read 551584 cycles
Wed Apr 30 21:06:47 2008 cycles contain 1850780 unique relations
Wed Apr 30 21:09:07 2008 read 1850780 relations
Wed Apr 30 21:09:19 2008 multiplying 2782286 relations
Wed Apr 30 21:14:33 2008 multiply complete, coefficients have about 84.20 million bits
Wed Apr 30 21:14:34 2008 initial square root is modulo 1105861
Wed Apr 30 21:21:26 2008 prp80 factor: 34957698771189765331782973598371343662802452976654329112913699889505994900648923
Wed Apr 30 21:21:27 2008 prp97 factor: 2306747025295127756657870419577411038780260831935613811132503821954020694612281320931385429666039
Wed Apr 30 21:21:27 2008 elapsed time 02:47:50

- ben.

maxal · 2008-05-01, 03:10

Would anybody be willing to complete factorizations of some numbers of the form 2^x - 3 that are specified in http://www.immortaltheory.com/NumberTheory/2nm3_db.txt

They may lead to new solutions to the congruence 2^n == 3 (mod n). See http://www.immortaltheory.com/NumberTheory/ for details.

Andi47 · 2008-05-02, 10:17

Quote:

Originally Posted by maxal

Would anybody be willing to complete factorizations of some numbers of the form 2^x - 3 that are specified in http://www.immortaltheory.com/NumberTheory/2nm3_db.txt

Have these numbers been p-1'ed and p+1'ed? If yes, to what extent? How much ecm did they have?

R.D. Silverman · 2008-05-02, 11:34

Quote:

Originally Posted by maxal

Would anybody be willing to complete factorizations of some numbers of the form 2^x - 3 that are specified in http://www.immortaltheory.com/NumberTheory/2nm3_db.txt

They may lead to new solutions to the congruence 2^n == 3 (mod n). See http://www.immortaltheory.com/NumberTheory/ for details.

There are enough projects already.

fivemack · 2008-05-31, 08:09

Fibonacci(1079) has 13 dividing the index, which leads to the rather hairy SNFS polynomial

Code:

X6  233
X5  -924
X4  330
X3  2630
X2  -3230
X1  361
X0  547
Y0  29518856641470372602077458635151025
Y1  -9839618880490124200692486211717008

where Y1 is 1-fibonacci(83)^2 and Y0 is fibonacci(82)^2+fibonacci(84)^2

SNFS difficulty around 208, so used 29-bit large primes, 24-bit small primes, sieved 16*2^20 to 28.5*2^20 on both rational and algebraic sides at about 53 CPU-hours per 2^20 per side. 3898433 x 3898681 matrix of sparse weight 237324495 took about 33 hours on a quad-core, four dependencies at about 100 minutes each to get

Code:

prp77 factor: 18727110802459085713612355138358090816535653522436895514996063854215718011073
prp77 factor: 44880947869994501075054379581241898325627426706522382877689328360578549344673

Definitely logistically easier by SNFS than a 153-digit GNFS, I don't know how it compares in time terms.

fivemack · 2008-06-30, 17:27

1061 is prime; Fibonacci(1061) is

Code:

93514417 *
43560958890354764963930018391355194517824960526673705978607400537437661703590480182627863527694377 *
59762024502667954496467866668111126040902657986182974323716858091462517843782397838677155890803832980467807587783629

I seem to be getting more nice large second-largest-factors out of Fibonacci than out of Cunningham numbers, but I'm sure this is coincidence.

alpertron · 2008-06-30, 20:08

Quote:

Originally Posted by fivemack

1061 is prime; Fibonacci(1061) is

Code:

93514417 *
43560958890354764963930018391355194517824960526673705978607400537437661703590480182627863527694377 *
59762024502667954496467866668111126040902657986182974323716858091462517843782397838677155890803832980467807587783629

I seem to be getting more nice large second-largest-factors out of Fibonacci than out of Cunningham numbers, but I'm sure this is coincidence.

...unless these are instances of Aurifeuillian-related factorizations. How many Fibonacci numbers of the form Fn = k*Pm*Pm (Pm = prime m-digits long) have you found?

2008-03-20, 00:29	#12
FactorEyes Oct 2006 vomit_frame_pointer 2³×3²×5 Posts	Can't resist -- an undeserved p47 Way back, working on 4^307+3^307. Only 1992 ECM curves at 3E6: Code: p47 = 14718260945227321993538833517239503165838463191 One word: gift Seems as if everyone enjoys splitting a composite into two primes of similar magnitude. A p60.p90 is just as good as a p72.p78, but there is something prettier about the latter.

2008-04-20, 05:31	#13
FactorEyes Oct 2006 vomit_frame_pointer 2³×3²×5 Posts	Dare to dream 5^292 + 4^292 has p50 factor 93172475798334091708528467222762440891545544410081. Personal best as far as SNFS magnitude goes, at 205 digits. 200 digits ain't what it used to be. Also, my first 3-fold split on an SNFS: 11^187 - 3^187: c154 = p47.p51.p57 p47: 92534718300915679831411055777591569981607096953 p51: 180166869627938348894812913800373604941787732024067 p57: 440853492502687501432544008137866572998304338991768202689 Gratuitous? You bet.

2008-05-31, 08:09	#20
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2·7·461 Posts	Fibonacci(1079) has 13 dividing the index, which leads to the rather hairy SNFS polynomial Code: X6 233 X5 -924 X4 330 X3 2630 X2 -3230 X1 361 X0 547 Y0 29518856641470372602077458635151025 Y1 -9839618880490124200692486211717008 where Y1 is 1-fibonacci(83)^2 and Y0 is fibonacci(82)^2+fibonacci(84)^2 SNFS difficulty around 208, so used 29-bit large primes, 24-bit small primes, sieved 162^20 to 28.52^20 on both rational and algebraic sides at about 53 CPU-hours per 2^20 per side. 3898433 x 3898681 matrix of sparse weight 237324495 took about 33 hours on a quad-core, four dependencies at about 100 minutes each to get Code: prp77 factor: 18727110802459085713612355138358090816535653522436895514996063854215718011073 prp77 factor: 44880947869994501075054379581241898325627426706522382877689328360578549344673 Definitely logistically easier by SNFS than a 153-digit GNFS, I don't know how it compares in time terms. Last fiddled with by fivemack on 2008-05-31 at 08:17

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Gratuitous OPN factors	wblipp	Factoring	463	2019-05-30 07:19
Ungracious Factors Thread	FactorEyes	Factoring	2	2011-04-09 05: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

2008-05-01, 03:10	#17
maxal Feb 2005 100000100₂ Posts	Would anybody be willing to complete factorizations of some numbers of the form 2^x - 3 that are specified in http://www.immortaltheory.com/NumberTheory/2nm3_db.txt They may lead to new solutions to the congruence 2^n == 3 (mod n). See http://www.immortaltheory.com/NumberTheory/ for details.

2008-06-30, 17:27	#21
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6454₁₀ Posts	1061 is prime; Fibonacci(1061) is Code: 93514417 * 43560958890354764963930018391355194517824960526673705978607400537437661703590480182627863527694377 * 59762024502667954496467866668111126040902657986182974323716858091462517843782397838677155890803832980467807587783629 I seem to be getting more nice large second-largest-factors out of Fibonacci than out of Cunningham numbers, but I'm sure this is coincidence.