mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

Reply
 
Thread Tools
Old 2007-04-14, 13:17   #1
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

4568 Posts
Post 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
nuggetprime is offline   Reply With Quote
Old 2007-04-16, 04:25   #2
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by nuggetprime View Post
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.
geoff is offline   Reply With Quote
Old 2007-04-16, 13:11   #3
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

1001011102 Posts
Default

Hmmm... Thanks for the algorithm,geoff.
I'll look into it later.
But is this algo already used?

nuggetprime
nuggetprime is offline   Reply With Quote
Old 2007-04-17, 03:10   #4
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

22058 Posts
Default

Quote:
Originally Posted by nuggetprime View Post
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.
geoff is offline   Reply With Quote
Old 2007-04-18, 14:49   #5
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2·151 Posts
Default

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
nuggetprime is offline   Reply With Quote
Old 2007-04-20, 04:19   #6
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

Quote:
Originally Posted by nuggetprime View Post
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
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
TF algorithm(s) davieddy Miscellaneous Math 61 2011-07-06 20:13
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
New Multiplication Algorithm vector Miscellaneous Math 10 2007-12-20 18:16
Using p=2 for sieving (Quadratic sieve algorithm) R1zZ1 Factoring 36 2007-11-02 15:59
Dixon's algorithm 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.