Factoring
Eric Hughes
hughes at ah.com
Sat Jul 16 10:23:34 PDT 1994
Factoring keeps being described as a 2^(n/2) problem, yet AFAIK
[...], it's doable in linear (O(n)) time.
Remember that the 'n' is the length of the input.
/* Algorithm: To factor the number n, start with n boxes, each with on
"marble." Remove last box, put it's marble in box #1. If all boxes
have the same number of marbles, the number is factored. If not,
remove last box. Put marble in box #2. Compare. Etc.
possible optimizations: div by each prime l for a quicker starting
point. (2,3...)
*/
This algorithm is equivalent to trial division by each number less
than n. At each stage the 'box counter' is equal to the remainder and
the 'number of boxes' is the divisor.
Now since n can be encoded in lg n bits (lg = base 2 logarithm), the
length of the input is N = lg n. The representation of the boxes can
be represented in O(N) bits; use two counters, each the length of the
input. The number of trial divisors is about 2^N, yielding an
exponential time algorithm.
Eric
More information about the cypherpunks-legacy
mailing list