Re: latency of hardware modular multiplication operation

From: Jan Panteltje (pNaonStpealmtje_at_yahoo.com)
Date: 02/26/04 

Date: Wed, 25 Feb 2004 23:36:19 GMT

On a sunny day (Wed, 25 Feb 2004 21:13:22 GMT) it happened "Tao Zhang"
<taoz@earthlink.net> wrote in
<Sd8%b.20317$W74.5261@newsread1.news.atl.earthlink.net>:

>Hi, Jan
>
>Thanks for the help. Maybe the number of the cycles is not the
>right thing to ask. I want to know the delay of modular multiplication
>algorithm, maybe in ns. I found some references. It looks
>modular multiplication can be reduced to additions. But there will be n
>additions for n-bit number. I am not sure what's the absoulte delay
>for a n-bit addition with the modern IC technology. Do you have
>any experience? I am using 256 bit numbers.
>
>Thanks a lot!
>
>Tao
Well, the fastest experience I have is with FPGA (programmable gate arrays).
An addition takes in the order of 1 nS perhaps less, these things get faster
all the time.
You must sort of get some understanding of the way this is done.
For example to 'multiply by 2' you can just take a 265 bit register,
and connect bit 0 of the input to bit 1 of the output, (bit 0 of the output
is made zero).
And then proceed.
In fact you do a shift left.
(Basically crossing wires!).
In this case *you loose no time*, the multiplied x 2 result is on those
wires!
Do this 2 x and you have x 4 see?
Multiplexing, so 3 shifts (x 8) and 2 additions will give you the result x
10.
The real time it takes is the time for the electrons to move, slightly
slower then the speed of light.
So you will never be faster then the area you use up dictates, if your
signals travel through 1mm wire, that is already the theoretically fastest
way (light 300000 km/s).
But electron speed is slower in metal conductors.
There are also such things as capacitance etc.
So I cannot give you a minimum.
There exist exotic semiconductors that you could use to make an INCREDIBLE
fast multiplier.
Still 256 bit x 256 bit -> 512 bits result? that is a lot.
If you do a web search for Josephson (think it was called) switches, these
work in the pico seconds range.
One could make a multiplier with that I am sure..
This is all I know about those high speed things.
Maybe someone who knows more can follow this up?
JP

Relevant Pages

  • Re: Starting out without gravity creates Boundries
    ... You got it right but its the time delay due to time being slower that's ... meter stick that must be smaller percentage of a meter long, ... down it must also shift into a higher frequency more energetic photons. ...
    (sci.physics)
  • Re: Starting out without gravity creates Boundries
    ... You got it right but its the time delay due to time being slower that's ... meter stick that must be smaller percentage of a meter long, ... down it must also shift into a higher frequency more energetic photons. ...
    (sci.physics.relativity)
  • Re: I dont believe it - iBook problems
    ... > You have mail - sorry for the delay. ... >> takeapart is fairly minimal if just replacing the inverter. ... >> PDF for that? ... wires I had to try four times before I got the case top back on ...
    (uk.comp.sys.mac)
  • Re: 100m JTAG cable
    ... jtag access. ... Perhaps even make the delay configurable via ... 'All' FPGA software could have issues, but yes, there IS a strong case for placing this level of software on sourceforge. ... That means the designer community can do slower,, JTAG variants. ...
    (comp.arch.fpga)
  • Re: RC Transmission Lines (Wafer-Scale)
    ... Guy Macon wrote: ... style interconnects are achieved by routing signal wires in the thicker top metal M6 layer and utilizing a metal M4 ground return plane to realize near velocity-of-light data transmission. ... The nominal wire delay is measured to 52.8ps corresponding to 32% of the velocity of light in vacuum. ... I sure as all heck do not call 32%" of Cas being anyway "near velocity-of-light delay". ...
    (sci.electronics.design)
Loading