Results 1 to 21 of 21

Thread: FPGA siever?

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Senior Member
    Join Date
    Jun 2005
    Location
    London, UK
    Posts
    271
    Nothing yet, I've been a bit busy at work and also outside work (spent the weekend at Lord's watching us get thrashed by Australia).

    Now I understand it more I can modify the algorithm to remove the decrement:-

    k*2^n+1 = 0 (mod p)
    k*2^n = -1 (mod p)
    2^n = -1 * (k^-1) mod p

    The server-PC side of the system will calculate -1 * k^-1 (mod p) for each of the k values, remove any candidates by checking the quadratic residues (as described by akruppa) and then pass these to the FPGA.

    This means that I just have to keep left shifting and possibly subtracting p and also checking that the value is one of the 9 search values.

    I'll see what I can do in the next month but free time is pretty rare...

    [EDIT] Further to this, I should be able to do something to help Riesel sieve at the same time, and possibly even PSP as each of these reduces to solving the Discrete Log equation 2^n = <some_value> (mod p).

    Due to the inherent parallel nature of FPGAs I can check for the current LHS value against many values without any performance hit. The problem becomes checking for many values as this may take up more 'space' on the FPGA reducing the number of sievers that can be placed on one FPGA and therefore reducing the overall performance of the FPGA as a whole.

    [EDIT 2] I had a chance meeting in a pub with someone who works with FPGAs and was able to pick their brains about an FPGA proth/riesel sieve.

    Everything looks good, I have a few pointers on things and two recommended books on order from Amazon. I should have a prototype (that would run a hardcoded p value) in a couple of weeks. From then I have to implement the memory interface, the serial interface on both the FPGA and the controlling PC and then see how many sievers I can get on one FPGA.

    I may even be able to implement the Baby-Steps Giant-Steps algorithm in an FPGA and that would be insanely fast. It's a completely different way of thinking about things when you have some much parallel processing available.
    Last edited by Greenbank; 07-26-2005 at 08:04 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •