From: norm@netcom.com (Norman Hardy)
Date: Fri, 12 Aug 94 18:35:51 PDT
To: Phil Karn <karn@qualcomm.com>
Subject: Re: IDEA vs DES
Message-ID: <199408130136.SAA21956@netcom.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


This morning I said:
>would expect that it can be done in under 100 microseconds. Modular
>>exponentiation of 1000 bit numbers should take about 2*(1000/24)^3
>>(1/30,000,000MHz) = 2.5 ms without outer loop overhead.

Sorry, I goofed! Thanks to Phil Karn for catching me on this. I omitted a
factor of 12 which is half of the number of bits in one of my "words". With
24 bits per word the 601 could do a 1000 bit by 1000 bit multiply in
(1000/24)^2 fmadd instructions, plus several times (1000/24) fixed point
instructions. The fmadd takes 2 clocks. Doing the modular multiply requires
about twice as much. Exponentiating by an n bit number requires about n/2
modular multiplies worst case. Doing mod(n^k, m) for 1000 bit numbers thus
requires about 2*2*(1000/24)^2*1000/2 clocks. For the slowest (60MHz) 601
this is 58ms.