20051011, 17:22  #1 
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×937 Posts 
17 or Bust
Hi,
I am not a member of the 17orbust effort. When I tried to send email from their web site, it insisted that I provide my member number....... Does anyone have a contact email address? I would like to discuss the technical details of their sieve procedure with them. I hope that at the minimum, they are doing the following: Observe that if a prime p divides k*2^n + 1, then 2^n = 1/k mod p, whence we have 2^(n + j*phi(p)) = 1/k mod p for all j. This gives a VERY efficient sieve procedure for eliminating a lot of candidates without trial division... I hope that they are using this procedure, or something similar. 
20051011, 18:10  #2 
Dec 2004
453_{8} Posts 
Dr Silverman,
Seventeenorbust SoB is basically using Klassons proth sieve, so your probably better off directing specific "proth sieve" questions towards him. He may even send you the source code. Uncertain if this is his most recent email but: mklasson (Shift2) acm (period) organization On another note, a collective group is currently working on a new sieving program. Some information can be obtained through the forums, however it is a work in progress and conducted mostly by email. http://www.freedc.org/forum/forumdi...?s=&forumid=38 Here is also a more specific thread were you can download the most recent beta version if your interested. http://www.freedc.org/forum/showthr...threadid=10069 If you'd like to contact Joe_O you can try emailing factrange@yahoo.com Last fiddled with by VJS on 20051011 at 18:13 
20051011, 18:21  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I participated in a brief discussion of their sieving algorithm in thread http://www.mersenneforum.org/showthread.php?t=4310
In short, yes, they compute discrete logarithms and use that to sieve over exponents. Alex 
20051011, 19:03  #4 
"Robert Gerbicz"
Oct 2005
Hungary
1,597 Posts 
They are using a baby stepgiant step algorithm for sieving k multiple values. Running time of this simple version is O(sqrt(k*interval)) for 1 prime number if we are sieving k multiple values for a<n<a+interval. For speed up this you can use small prime power divisors of p1.
I have written a very efficient speed up using this in june 2003. You can find the description of this algoritm in my post http://www.freedc.org/forum/showthr...9254#post29254 Note that they are using this algorithm for multiply k sieving. 
20051011, 20:54  #5  
Aug 2002
20D_{16} Posts 
Quote:


20051011, 21:10  #6  
Aug 2002
20D_{16} Posts 
Quote:
What definition of phi are you using? Could you provide a proof for the above? The definition of phi that I am most familiar with is: phi(N) is the number of primes less than or equal to N Now if we define o2p(p) as the order of 2 in Zp, I am familiar with the fact that 2^(n + j*o2p(p)) = 1/k mod p for all j if 2^n = 1/k mod p. And yes this is made use of. Also please note that 2^n = 1/k mod p gives us the requirement that for n even, k must be a quadratic residue of p; and for n odd, 2k must be a quadratic residue of p. This also is made use of. 

20051011, 21:39  #7 
Aug 2002
3×5^{2}×7 Posts 
Never mind Dr Silverman. I just realized that you were using Euler's Totient function phi(n) which is defined as the number of positive integers that are relatively prime to n (i.e., do not contain any factor in common withn) , where 1 is counted as being relatively prime to all numbers. For this function phi
phi(p) = p1 for all prime p and yes by Fermat's Little Theorem 2^(p1)==1 mod p for prime p, so your statement holds. Note that the order of 2 that I mentioned, is defined as the least n such that 2^n == 1 mod p. It can be shown that the order of 2 is a factor of p1.... 
20051011, 21:42  #8  
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}×5×7 Posts 
Quote:
Quote:


20051011, 23:48  #9 
"Robert Gerbicz"
Oct 2005
Hungary
1,597 Posts 
Fast multiple k sieving
There is a really fast algorithm to find prime divisors for multiple k sieving problem. The only problem is that the memory requirement is ( very ) large for a PC. However this algorithm isn't very new:
we can find small factors of a sequence see section 20. in this excellent paper by D. J. Bernstein: http://cr.yp.to/lineartime/multapps20041007.pdf using FFT for multiplication, divison and gcd. Suppose that we have integers h(1),h(2),...,h(s) and f(1),f(2),...,f(t) and we want to find which f(i)'s divide h(1) and so on. Then running time of this algorithm is O(u*log(u)^3*loglog(u)), where u is the total number of input bits. In our case: Suppose that we have k different values in sieving and we have sieved up to p and we want to sieve a(i)*2^b+1 where i=1,2,..,k and 1<b<n. If we have sieved up to p then there are only O(n/log(p)) numbers which are survived sieve up to n for a single k value .We've k different values and remaining numbers has got O(n) bits, so these numbers has got altogether O(k*n^2/log(p)) bits, we want to minimize the average cost for a single p prime number so the best choice is that if number of bits of h(1),h(2),...,h(s) sequence and number of bits of f(1),f(2),...,f(t) sequence is the same so: O(k*n^2/log(p))=t*O(log(p)) // because we have sieved up to p, so we will sieve q>p values where it has got O(log(p)) bits. Solving this: t=O(k*n^2/log(p)^2). So we are always testing t different prime numbers at once! Input numbers has got u=O(k*n^2/log(p)) bits, but we are testing t different prime numbers at once so the average time for a single p prime number: O(u*log(u)^3*loglog(u))/t<= <=O(k*n^2/log(p)*log(k*n)^3*loglog(k*n))/O(k*n^2/log(p)^2)= =O(log(p)*log(k*n)^3*loglog(k*n))= =O(log(p)*log(n)^3*loglog(n)) ( I have made some assumption to get this small formula: here k<n ). and this is much smaller then all of other methods : those has got running time O(sqrt(k*n)) but this running time is only O(log(p)*log(n)^3*loglog(n)). Bad news is that we need O(k*n^2*log(n)/log(p)) bits of memory to build up the binary tree for multiplications and for divisons. We can gain O(log(n)) factor in memory cost if we lost O(log(n)) factor in speed ( don't store binary tree, just store product of h(1)*h(2)*...*h(s) then compute in every step the required number in divison/gcd routine. ) 
20051012, 02:42  #10  
Aug 2002
3×5^{2}×7 Posts 
Quote:
There are at least two contradictory definitions of phi. eg see http://www.math.utah.edu/~alfeld/math/machine.html where phi(n) is defined as the number of primes less than n or equal to n For the sake of conciseness and accuracy a non obfuscatory person should either state that they are referring to Euler's phi and not some other definition, or simply put p1 where they mean p1. Would it have been so hard to write 2^(n + j*(p1)) = 1/k mod p for all j when that is what was meant? I'm all for accuracy, conciseness and clarity in mathematics. Would this have been any less accurate, concise or clear? And yes this statement is of much more use when p is smaller. We are only sieving for n < 100M and there are very few p in the range that we are sieving that would have an order of 2 < 100M so that we would have two or more n's <= 100M ie n1 and n2 where n2 = n1+j*(p10 for some j. If there are any other consequences of this that would help sieving, I would request that someone post them here so that we may discuss them and possibly put them to use if we have not already done so. Last fiddled with by Joe O on 20051012 at 02:48 

20051012, 04:03  #11 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001100000_{2} Posts 
pi(N) is usually defined as the number of primes less than or equal to N, phi(N) is not the standard notation.
Note that our postings occurred at almost the same time. I hadn't overlooked your posting, it just hadn't shown up yet. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fourteen or Bust, or ECM attack on C300+  XYYXF  XYYXF Project  32  20220723 02:31 
Seventeen or Bust drive  philmoore  Lounge  6  20140526 23:10 
17 or bust  get restarted  Jud McCranie  PrimeNet  3  20140427 04:25 
Five or Bust  hhh  Lounge  1  20081010 15:26 
Seventeen or Bust found a prime!  Mystwalker  Math  5  20050104 17:00 