mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-04-07, 23:18   #45
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

1005410 Posts
Default

Even smaller, which are for example 98-105 digit SNFS jobs.
Don't forget SNFS jobs. They are fun, and a good excercise for the mind (to build a polynomial in some cases; in most cases of course - it's a boring excercise for boring polynomials). Some Fibonacci numbers have very nice polynomials, and so do e.g. numbers of form a^13n+-b^13n, and Aurifeuillians and so on, and so on.

In those 98-105 digit SNFS jobs, if you will have oversieved (using 0.4 or 0.5), the filtering will fail to converge and the script will stop (it's fixable, too, - check the similar threads). If you use 0.2 with those jobs, you will converge in a ridiculously short time, like 5 or 10 minutes for the whole factorization. Like this one:
Code:
 
n: 142636039930449499515055724706069369122952024169034908419840194033346894320140545970889557
c4: 7
c0: 11
Y1: 1
Y0: -10000000000000000000000000
skew: 1.12
type: snfs
lss: 1
rlim: 400000
alim: 400000
lpbr: 25
lpba: 25
mfbr: 45
mfba: 45
rlambda: 2.2
alambda: 2.2
Note: it will choke with 0.4. (And it will choke, too, if you use double qintsize jumps with 4 threads in factMsieve.pl.)
Compare that to the times of mpqs or gnfs.
Batalov is offline   Reply With Quote
Old 2009-04-07, 23:26   #46
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·11·457 Posts
Default

...or take this one for example (someone couldn't quite finish it)...
Code:
n: 7126956154329172964190407581733579595542753084022720093873577878288167714232922899398415101
m: 200000000000000000000000000
deg: 4
c4: 13
c0: 44
skew: 1.36
type: snfs
lss: 1
rlim: 410000
alim: 410000
lpbr: 25
lpba: 25
mfbr: 45
mfba: 45
rlambda: 2.2
alambda: 2.2
It's a 10 minute job, man. 10 minutes, tops!

Last fiddled with by Batalov on 2009-04-07 at 23:36
Batalov is offline   Reply With Quote
Old 2009-04-08, 00:11   #47
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

186916 Posts
Default

Quote:
Originally Posted by Batalov View Post
...or take this one for example (someone couldn't quite finish it)...
Code:
n: 7126956154329172964190407581733579595542753084022720093873577878288167714232922899398415101
m: 200000000000000000000000000
deg: 4
c4: 13
c0: 44
skew: 1.36
type: snfs
lss: 1
rlim: 410000
alim: 410000
lpbr: 25
lpba: 25
mfbr: 45
mfba: 45
rlambda: 2.2
alambda: 2.2
It's a 10 minute job, man. 10 minutes, tops!
Ah, seems that "someone" sent me that one as well. I reserved it at the near-repdigit website shortly afterwards and finished it in...hmm, come to think of it, I forgot to take note of how much time it took and have since deleted the log. Oh well, the log will show up on the near-repdigit website's progress update tomorrow at 5 P.M. GMT.

I ended up finishing it with factLat.pl after postprocessing with msieve just wouldn't work no matter how much relations I limited it to. I got the window between "filtering wants more relations" and "matrix not dense enough" down to a window of 100 relations, and it still wouldn't work, so I gave up and did it with factLat.pl.

(Note: this was done with an unmodified factMsieve.pl, downloaded a month or so ago. I really should update to the latest new-and-improved one some time soon...not sure if it would help in this particular instance though.)

Last fiddled with by mdettweiler on 2009-04-08 at 00:12
mdettweiler is offline   Reply With Quote
Old 2009-04-08, 00:30   #48
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100111010001102 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
I ended up finishing it with factLat.pl after postprocessing with msieve just wouldn't work no matter how much relations I limited it to. I got the window between "filtering wants more relations" and "matrix not dense enough" down to a window of 100 relations, and it still wouldn't work, so I gave up and did it with factLat.pl
Right. That shows that maybe 0.2 should have been changed to 0.15 for this one.

You know what could have happened with your trimming? msieve adds "free" rels. if you trim these away, nothing will change in the next filtering run - they will be simply added back in.
Ok, and here's a trick from the bottom of my sack. 1. trim .dat file and also 2. edit the .job file! decrease by 10 the "q0" that's there. This is necessary to deceive the siever not to sieve, because otherwise it will sieve a bunch again and you will have trimmed in vain.

This necessary number of relations (MINRELS) is so tricky that no one really wants to touch this 0.2 parameter in the downloadable script! At the very least 0.2 works almost always (if only not for this number).
Here's the necessary magic to finish fiascos like this (trimming extra relations from the bottom of the .dat file... but not too many ... how many is not too many? nobody really knows!) -
http://mersenneforum.org/showthread.php?t=11585
and bits of the same advice in three or four more threads... This does plague little numbers and not medium and large numbers. If you are working on a day-week scale jobs, then 0.5 is the coefficient you almost always need.

the MINRELS.txt patch was supposed to help (mostly for larger numbers); but if the number is tiny, then put 1 in the MINRELS.txt file -- that shouldn't hurt.

Last fiddled with by Batalov on 2009-04-08 at 00:48
Batalov is offline   Reply With Quote
Old 2009-04-08, 01:54   #49
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

Quote:
Originally Posted by Batalov View Post
You know what could have happened with your trimming? msieve adds "free" rels. if you trim these away, nothing will change in the next filtering run - they will be simply added back in.
Ok, and here's a trick from the bottom of my sack. 1. trim .dat file and also 2. edit the .job file! decrease by 10 the "q0" that's there. This is necessary to deceive the siever not to sieve, because otherwise it will sieve a bunch again and you will have trimmed in vain.
Regarding the "free" relations: hmm, interesting. I hadn't thought of that. Next time I'll be sure to pay closer attention to that when I need to trim relations.

Regarding the little trick of "fooling" factMsieve.pl into not sieving any more: yes, I've used that a few times. However, in this case it wasn't necessary since, in reality, I was simply running msieve directly (though with the exact same command line that factMsieve.pl had originally tried to feed to it, with modifications where necessary to make it chop off additional relations).
mdettweiler is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
P-1 B2 time estimates henryzz GMP-ECM 8 2009-12-31 17:51
c97 GNFS not possible? Andi47 Msieve 5 2009-01-26 18:19
Chebyshev's Estimates brownkenny Math 2 2009-01-22 17:21
Msieve QS estimates henryzz Msieve 27 2009-01-21 18:37
Accuracy of completion date estimates? kdq Software 4 2008-10-04 05:02

All times are UTC. The time now is 21:22.


Wed Feb 1 21:22:41 UTC 2023 up 167 days, 18:51, 0 users, load averages: 0.75, 0.85, 0.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔