View Single Post
Old 2007-08-01, 03:11   #50
Citrix's Avatar
Jun 2003

30478 Posts

I have looked into couple of things regarding making srsieve faster.

1) I have found a way to implement pollard rho with only ~2*sqrt(x) multiplications for each prime.

There are 2 problems though a) We will not able to combine the steps so each k will be done separately. b) There is no way to limit the sieve to only values under 50M, unless you use SPH.

So basically if time saved from writing things in memory and reading them later is more than doing all k's separately then this method will be useful, otherwise there is no point implementing it.

It might help on machines that have low memory, but the BSGS loop takes little memory from what I understand and the initial sieve takes the most memory. The other place where this could be useful is in sr1sieve, but we will have to use SPH.

2) The only other way we can speed up things is using SPH with BSGS. If I write the code for Chinese Remainder Theorem and some of the other things that the program will need, do you think we can make the program faster?

Last fiddled with by Citrix on 2007-08-01 at 03:45
Citrix is offline   Reply With Quote