## Factoring By Digital Coding

### April 1, 2014

Here’s our version of the program; `bits`

and `unbits`

convert between binary and decimal, `dc`

performs a single digital coding step, and `dc-factor`

searches for a factor:

`(define (bits n)`

(if (zero? n) (list 0)

(let loop ((n n) (bs (list)))

(if (zero? n) bs

(loop (quotient n 2)

(cons (modulo n 2) bs))))))

`(define (unbits bs)`

(let loop ((bs bs) (n 0))

(if (null? bs) n

(loop (cdr bs) (+ (* n 2) (car bs))))))

`(define (dc n)`

(unbits (mappend bits (digits n))))

`(define (dc-factor n)`

(let loop ((d (dc n)))

(display d) (display " ")

(let ((g (gcd d n)))

(if (< 1 g n) g

(loop (dc d))))))

And here are the examples from the article:

`> (dc-factor 88837)`

69919 54073 2847 2599 5529 2921 333 37

> (dc-factor 96577)

40319 23

We used `mappend`

and `digits`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/XyNkafVD.

By the way, this algorithm is completely bogus. It doesn’t factor anything; those results we obtained we just by chance. Happy April Fool’s Day!

Pages: 1 2

I use the cycle-finding method from Pollard’s Rho algorithm to check whether we’re stuck in a loop.

While fast, this has a disturbingly high failure rate: 338,793 out of the first million natural numbers fail to produce a factor by this method.

I suppose it might be useful as a prefilter when attempting to factor large numbers with no small factors — it’s a computationally cheap procedure, so it wouldn’t introduce much overhead and has a chance of dramatically speeding up the task by skipping the heavy artillery such as the ECM or MPQS if it succeeds.

@Lucas: Did you see the last paragraph on the second page of the exercise?

The following is my Mathematica code:

1. Firstly define a function that create the digital code of a specific number:

2. Then a function that computes successive digital codes until a gcd is greater than 1 is defined as follows:

3. Finally, define a function that returns the expected results:

In Mathematica, we get: