Combine sieving with SoB? - Page 4

VJS · 2005-07-12, 19:00

Well your going to be in for a butt load of updating if you decide to go public this quickly. You should look at the factor density graph in the sob link I posted earlier. The dat can certainly be knocked down to 60% of the original size within 1T (I think).

I just say do it slow do it right the first time and check check check the last thing you want to do is make a mistake.

Good luck

Citrix · 2005-07-13, 19:11

hhh,
Is there a webpage where I can see at what g SOB is at for their 20-50M dat? I couldn't find anything on the forum.

Just want to know till where we have to catch up.

Citrix

VJS · 2005-07-13, 20:27

Citrix,

Basically we have everything less than 100T sieved except for the following holes.

53000-57000
69000-76000
80000-89000
90000-95000

Also many ranges above 600T have already been sieved with 991-50M and we are going to try to sieve everything from 900T upward with 991-50M.

ltd · 2005-07-13, 21:17

I think it would be sufficient to catch up to something around 35-45T. Then the dat file is stable enough that a combined effort really makes sence.

VJS · 2005-07-13, 22:13

Even if you can get it to about 18T, I'd start using it on those 50-100T ranges incomplete.

I'm going recommend to people currently doing secondpass to simply continue with the 991-50M dat on first pass and hold off a bit on our SoB secondpass effort until we could combine.

akruppa · 2005-07-13, 23:20

I'm curious, how do you go about sieving for SoB? Do you determine the congruence n must satisfy that p | k*2^n+1 for given k, p?

Alex

VJS · 2005-07-14, 02:40

Alex,

We are honoured to have you in our thread

.
We are basically using Klassons proth sieve, PSP numbers and SoB numbers are of the same forum k*2^n+1. Simply a copy paste of the dats together is change the numbers of k's and that what we consider combining the sieve.

The actual %eff increase has yet to be determined but it will surely bet better than doing each set of k's seperate.

Quote:

congruence n must satisfy that p | k*2^n+1

Yes, but i'm neither a math nor proth sieve code expert.

Hopefully Joe_O will see this post and PM you if your thinking of optimizing the client itself.

Citrix · 2005-07-14, 11:30

Quote:

Originally Posted by akruppa

I'm curious, how do you go about sieving for SoB? Do you determine the congruence n must satisfy that p | k*2^n+1 for given k, p?

Alex

Basically proth_sieve uses the discrete log algorithm. Discrete log can be made faster for multiple k's because the portion that is common to all k's can be increased and the portion that is not common is reduced. Hence proth_sieve ends up to be faster than newpgen for multiple k's.

See the code I posted above if you are not sure about discrete log.

Citrix

akruppa · 2005-07-14, 12:01

Quote:

Originally Posted by Citrix

Basically proth_sieve uses the discrete log algorithm.

That's what I had been wondering about.

Quote:

Originally Posted by Citrix

See the code I posted above if you are not sure about discrete log.

Citrix

Ah, a giant-step-baby-step algorithm. Do you compare orders of 2 and -1/k to discard candidate factors early, or determine divisors of the logarithm?

Alex

Citrix · 2005-07-14, 12:13

Not sure what you mean? Please explain!

Citrix

garo · 2005-07-14, 13:49

Alex,
The person best qualified to answer that question in M. Klasson. I've sent him a PM with the URL of this thread. Hopefully, he will drop in.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Line sieving vs. lattice sieving	JHansen	NFSNET Discussion	9	2010-06-09 19:25
64-bit sieving	paleseptember	Five or Bust - The Dual Sierpinski Problem	16	2009-01-25 20:26
Should a diskless node run it's own ecm program or should I combine them somehow?	jasong	GMP-ECM	1	2006-02-24 08:34
Sieving	ValerieVonck	Math	9	2005-08-05 22:31
Sieving	OmbooHankvald	Prime Sierpinski Project	4	2005-06-30 07:51

2005-07-12, 19:00	#34
VJS Dec 2004 100101011₂ Posts	Well your going to be in for a butt load of updating if you decide to go public this quickly. You should look at the factor density graph in the sob link I posted earlier. The dat can certainly be knocked down to 60% of the original size within 1T (I think). I just say do it slow do it right the first time and check check check the last thing you want to do is make a mistake. Good luck

2005-07-13, 19:11	#35
Citrix Jun 2003 2×7×113 Posts	hhh, Is there a webpage where I can see at what g SOB is at for their 20-50M dat? I couldn't find anything on the forum. Just want to know till where we have to catch up. Citrix

2005-07-13, 20:27	#36
VJS Dec 2004 299₁₀ Posts	Citrix, Basically we have everything less than 100T sieved except for the following holes. 53000-57000 69000-76000 80000-89000 90000-95000 Also many ranges above 600T have already been sieved with 991-50M and we are going to try to sieve everything from 900T upward with 991-50M.

2005-07-13, 21:17	#37
ltd Apr 2003 2²×193 Posts	I think it would be sufficient to catch up to something around 35-45T. Then the dat file is stable enough that a combined effort really makes sence.

2005-07-13, 22:13	#38
VJS Dec 2004 453₈ Posts	Even if you can get it to about 18T, I'd start using it on those 50-100T ranges incomplete. I'm going recommend to people currently doing secondpass to simply continue with the 991-50M dat on first pass and hold off a bit on our SoB secondpass effort until we could combine.

2005-07-13, 23:20	#39
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	I'm curious, how do you go about sieving for SoB? Do you determine the congruence n must satisfy that p \| k*2^n+1 for given k, p? Alex

2005-07-14, 12:13	#43
Citrix Jun 2003 2·7·113 Posts	Not sure what you mean? Please explain! Citrix

2005-07-14, 13:49	#44
garo Aug 2002 Termonfeckin, IE 2²·691 Posts	Alex, The person best qualified to answer that question in M. Klasson. I've sent him a PM with the URL of this thread. Hopefully, he will drop in.