[107809] in Cypherpunks
Re: CDR: A digital way to filter...
daemon@ATHENA.MIT.EDU (Bill Stewart)
Sun Jan 24 17:44:49 1999
Date: Sun, 24 Jan 1999 14:30:49 -0800
To: Jim Choate <ravage@einstein.ssz.com>, cypherpunks@einstein.ssz.com
From: Bill Stewart <bill.stewart@pobox.com>
In-Reply-To: <199901242046.OAA00997@einstein.ssz.com>
Reply-To: Bill Stewart <bill.stewart@pobox.com>
At 02:46 PM 1/24/99 -0600, Jim Choate wrote:
>
>Hi,
>
>One possible way would be to create an array of counters whose stages map to
>the primes. Then feed it a pulse train of n pulses. If none of the counters
>end up with any remainder then the number should be prime.
>
>This should be doable in standard FPGA's and such. This should be a
>reasonably fast way to factor numbers. We only need to prove we know all the
>primes, k, less than n. With k counters set to those primes we should be
>able to factor n in at most n clock cycles.
>A linear factoring algorithm?
First of all, linear in n is exponential in log2 n,
which is what matters here (assuming you're factoring numbers
on the order of 1024 bits long, rather than numbers up to 1024...)
Also, you need exponentially many counters, so linearity is irrelevant :-)
(Hint: How many primes are less than 2**1024?)
Do you have a particular planet you're planning to store this on?
Of course, once you've built them, how do you distribute n signals
to the k counters, and get the results back?
You could naively do this in linear-with-k time,
but you can get fancier and do it in log k time
(your choice of logarithm base, depending on how much fanout you can support.)
Thanks!
Bill
Bill Stewart, bill.stewart@pobox.com
PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
