sieving on GPU vs CPU

[Citrix]

Originally Posted by rogue

Unfortunately we are a way from doing that. BSGS needs too much memory so the GPU is not practical. Memory light methods are not very smooth.

This might be of some interest. I do not have access to the paper, so cannot say if it can be implemented on a GPU.

http://www.ams.org/journals/mcom/201...-2012-02641-X/

If any one has a copy could they PM it to me? Thx

[rogue]

Originally Posted by Citrix

This might be of some interest. I do not have access to the paper, so cannot say if it can be implemented on a GPU.

http://www.ams.org/journals/mcom/201...-2012-02641-X/

If any one has a copy could they PM it to me? Thx

If it is based upon Pollard Kangaroo, it is likely to be probabilistic not deterministic.

[henryzz]

Originally Posted by rogue

If it is based upon Pollard Kangaroo, it is likely to be probabilistic not deterministic.

For sieving we don't need to find every factor. The speed factors are found is much more critical.

[Citrix]

Originally Posted by henryzz

For sieving we don't need to find every factor. The speed factors are found is much more critical.

I agree. You sieve the low p ranges on a CPU and the higher p ranges on a GPU.

[rogue]

Originally Posted by henryzz

For sieving we don't need to find every factor. The speed factors are found is much more critical.

I do not have a heuristic on how percentage of factors will be missed vs how much faster a GPU version would be. In other words, if it is twice as fast, but misses 50% of the factors, it is a wash. I also stated before the there is an issue of "smoothness". I would have to exclude a number of p from being sieved in the GPU because they are not smooth. I would need the factorization of p-1 to know how smooth each p is and that would also impact throughput.

[rob147147]

I have written a GPU sieve using Pollard Lambda (Kangaroo) and while it is performance competitive to the CPU code over small ranges of n values it loses massive amounts of performance over larger ranges.

Its also worth noting that the Kangaroo method finds pretty much the same number of factors as the CPU BSGS code when run for enough loops but a slight reduction in the number of loops run can result in a massive fall in factors found

[Citrix]

Originally Posted by rogue

I also stated before the there is an issue of "smoothness". I would have to exclude a number of p from being sieved in the GPU because they are not smooth. I would need the factorization of p-1 to know how smooth each p is and that would also impact throughput.

The algorithms mentioned in the paper I cited, do not require p-1 to be smooth.
Though using the factors of p-1 might (or might not) make the program faster.

[Citrix]

I was able to find an online copy of the paper:-
https://eprint.iacr.org/2010/617.pdf