Re: [Ggnfs-devel] compressed relations

[Jason P. <ja...@bo...>]

Quoting Sten <st...@ma...>:

> So, I think we can analyze how sievers factor relations - they
> should have more optimal approach - and, maybe, mimic CWI-like
> behaviour saving only large factors.

Ideas mailed to Anton.

jasonp

-------------------------
I have a few ideas to increase factoring speed but they're all pretty 
complicated:

- use the heavy-duty ECM implementation. It should be able to split
  relations into several big pieces very quickly

- use some kind of resieving procedure to handle the larger factor
  base primes. Alternately, you can sort the list so that relations
  with the same b value are contiguous, then use the sieving root
  of each factor base prime to implement the divisibility test
  without multiple-precision arithmetic

- (enormous amount of work) Dan Bernstein has studied this problem a
  lot, and has several papers on his web page (cr.yp.to) that give
  what are asymptotically the fastest algorithms for solving this
  problem. Unfortunately they require FFTs and arithmetic on huge
  operands.

I think the best bet for a quick speedup is the sorting idea, but I
haven't looked at the patches yet. Note that if you don't know the
special-q from the lattice siever, the product of the large primes
can be up to 96 bits in size, and using MPQS to finish off that
cofactor means that the theoretical upper bound on the relation
processing rate is 100-200 relations per second.
----------------------------

------------------------------------------------------
This message was sent using BOO.net's Webmail.
http://www.boo.net/