0

I need to perform modular multiplication on two large numbers (more than 10,000 bits wide). I've found papers that give designs that can that calculate the result in N cycles, but in my case, that would take over 10,000 cycles to compute. How can it be done without iterating, preferably in a single cycle?

jsotola
  • 2,497
  • 2
  • 12
  • 21
Hisoka
  • 1
  • 6
    Is the requirement for a single cycle because you want it to be fast, or because you want it to be simpler without iterations? You could probably make a gigantic and extremely slow combinational multiplier that doesn't need a clock. – Justin Oct 25 '21 at 20:20
  • Can you elaborate on the application? A 10,000 bit number is huge. Are all of the digits in the answer significant or can you do an approximation? – Barry Oct 25 '21 at 22:37

1 Answers1

2

I think the best you can do is the Schönhage–Strassen algorithm which runs in \$O(n \log n \log \log n)\$ time and can be implemented in an FPGA: FPGA Based Schonhage Strassen Integer Multiplication Algorithm

D Duck
  • 2,041
  • 1
  • 8
  • 18