mersenneforum.org Maybe new sieving algorithm
 Register FAQ Search Today's Posts Mark Forums Read

 2007-04-14, 13:17 #1 nuggetprime     Mar 2007 Austria 4568 Posts Maybe new sieving algorithm I've found a maybe new sieving algorithm for riesel numbers. k is the k for riesels k*2^n-1 n is the n for riesels k*2^n-1 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=(p-1)*x+c for every x. for every k, some primes will never divide k*2^n-1. 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
2007-04-16, 04:25   #2
geoff

Mar 2003
New Zealand

13·89 Posts

Quote:
 Originally Posted by nuggetprime Step 2: find a c such that 2^c mod p = b.
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/Baby-step_giant-step.

 2007-04-16, 13:11 #3 nuggetprime     Mar 2007 Austria 1001011102 Posts Hmmm... Thanks for the algorithm,geoff. I'll look into it later. But is this algo already used? nuggetprime
2007-04-17, 03:10   #4
geoff

Mar 2003
New Zealand

22058 Posts

Quote:
 Originally Posted by nuggetprime But is this algo already used?
Yes, you have described pretty much how all the fixed-k 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^n-1.

 2007-04-18, 14:49 #5 nuggetprime     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
2007-04-20, 04:19   #6
geoff

Mar 2003
New Zealand

48516 Posts

Quote:
 Originally Posted by nuggetprime 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...
If you are testing prime p and find a solution c to 2^c = b (mod p), that will tell you whether or not p divides one of the terms k*2^n-1. But then why save c? What use will it be for any future prime you test? Remember c could be any number in the range 0 < c < p, and b is different for each different p.

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 2007-04-20 at 04:25

 Similar Threads Thread Thread Starter Forum Replies Last Post davieddy Miscellaneous Math 61 2011-07-06 20:13 JHansen NFSNET Discussion 9 2010-06-09 19:25 vector Miscellaneous Math 10 2007-12-20 18:16 R1zZ1 Factoring 36 2007-11-02 15:59 JHansen Factoring 5 2005-03-15 21:35

All times are UTC. The time now is 00:03.

Wed May 19 00:03:30 UTC 2021 up 40 days, 18:44, 0 users, load averages: 1.39, 1.44, 1.43