20070414, 13:17  #1 
Mar 2007
Austria
456_{8} Posts 
Maybe new sieving algorithm
I've found a maybe new sieving algorithm for riesel numbers.
k is the k for riesels k*2^n1 n is the n for riesels k*2^n1 p is the current prime for which the riesels are currently checked for factors. Step 1: find a b such that k*b mod p = 1. Step 2: find a c such that 2^c mod p = b. To avoid large numbers, you should do the following: 1.set c=2. 2.Then set c=(2*c) mod p Repeat step 2 so long that c=b. Then you could eliminate every n=(p1)*x+c for every x. for every k, some primes will never divide k*2^n1. That's the weight of the k, or? You could save c's for every p in a file to speed up sieving. Any errors/suggestions/infos: please reply here. nuggetprime 
20070416, 04:25  #2 
Mar 2003
New Zealand
13·89 Posts 
The interesting bit is how to carry out (or avoid the need for) this step, the discrete log problem.
Here is one way to carry it out: http://en.wikipedia.org/wiki/Babystep_giantstep. 
20070416, 13:11  #3 
Mar 2007
Austria
100101110_{2} Posts 
Hmmm... Thanks for the algorithm,geoff.
I'll look into it later. But is this algo already used? nuggetprime 
20070417, 03:10  #4 
Mar 2003
New Zealand
2205_{8} Posts 
Yes, you have described pretty much how all the fixedk sieves work, except that before step 1 (finding the inverse of k) there are some properties of k, e.g. the Legendre symbols of 2 and k with respect to p, that can sometimes be used to decide that p can never be a factor of any k*b^n1.

20070418, 14:49  #5 
Mar 2007
Austria
2·151 Posts 
Thanks geoff.
But you aren't using a file saving every c. Example: k=15. write c's to 25G to a file. Sou you could sieve every n range VERY fast, or? The only problem I guess is the large file size. Should be solved... nuggetprime 
20070420, 04:19  #6  
Mar 2003
New Zealand
485_{16} Posts 
Quote:
edit: Maybe you are sugesting save each value 2,2^2,...,2^c (mod p) to file? But these values will be different for each different p too. Last fiddled with by geoff on 20070420 at 04:25 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
Line sieving vs. lattice sieving  JHansen  NFSNET Discussion  9  20100609 19:25 
New Multiplication Algorithm  vector  Miscellaneous Math  10  20071220 18:16 
Using p=2 for sieving (Quadratic sieve algorithm)  R1zZ1  Factoring  36  20071102 15:59 
Dixon's algorithm  JHansen  Factoring  5  20050315 21:35 