Re: modular exponentiation in software

Subject: Re: modular exponentiation in software
From: Wei Dai (weidaieskimo.com)
Date: Wed Dec 01 1999 - 13:55:35 CST

• Next message: lcs Mixmaster Remailer: "Re: Lucre fixed?"
• Previous message: Eugene Leitl: "Re: Universal Quantum Computers"
• In reply to: Thomas Kenneth Zaplachinski: "modular exponentiation in software"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

On Tue, Nov 30, 1999 at 04:56:16PM -0700, Thomas Kenneth Zaplachinski wrote:
> Does anyone have any benchmarks for performing software modular
> exponentiation for different key lengths? What would be an acceptable
> length of time for performing g^x mod n where x is a random k-bit integer,
> n is a k-bit prime, and g is a random k-bit generator for the field Fn,
> for k=512, 1024, 2048, and 4096?

A good rule of thumb is the above operation takes roughly 100 ms for
k=1024 on a 400 MHz Pentium II. Multiply this by 6 for each doubling of k.

> Does anyone have a favorite large integer library (speed/ease of use).

I'm obviously biased, having written my own, so I'll let others answer this
one.

> If anyone knows how long these operations should take on modern PCs
> (ie Pentium II) I'd greatly appreciate any numbers I can get.

For more empircal data, I have a page with benchmarks of popular crypto
algorithms. It's at http://www.eskimo.com/~weidai/benchmarks.html.

• Next message: lcs Mixmaster Remailer: "Re: Lucre fixed?"
• Previous message: Eugene Leitl: "Re: Universal Quantum Computers"
• In reply to: Thomas Kenneth Zaplachinski: "modular exponentiation in software"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

This archive was generated by hypermail 2b27 : Wed Dec 01 1999 - 17:24:16 CST