objectivity and factoring analysis

Adam Back adam at cypherspace.org
Mon Apr 22 19:37:50 EDT 2002


Nicko writes:
> [...] the Bernstein proposal [...] (among other things) it details
> the conceptual design of a machine for computing kernels in a large,
> sparse matrix.  The design talks of the number of functional units
> and the nature of the communication between these units.  What I set
> out to do was look at how complex those units are and how hard it
> would be to connect them and to place a cost on this.
> 
> [...]
> 
> OK, here are the numbers I used [...] we should be able to find a
> kernel in somewhere around 10^7 seconds, which is 16 weeks or 4
> months.

For people who aren't following as closely I think it would be useful
to remind that this is an estimate of the building cost and running
time of one aspect of computation in the overal proposal.  (You give a
rough running-time estimate which some might misunderstand).

The _overall_ running time of the algorithm and whether it is even any
faster or more economical than existing algorithms remains _unknown_
due to the asymptotic result which the experiment is intended to
investigate.

If the hardware were to be built it might for example turn out that
the asymptotic result may only start to offer speedups at far larger
key sizes and if this were the case, depending on the results it could
be that the approach turns out to offer no practical speed-ups for the
for-seeable future.

Or it might turn out that it does offer some incremental improvement,
and even that key sizes should be increased.

But right now no one knows.

Adam

btw. As disclaimed in the original post no insult was intended --
merely more accurate information given the somewhat wild speculations.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list