## 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

### 4 Responses to “Factoring By Digital Coding”

1. Lucas A. Brown said

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

```def digital_coding(n):
if isprime(n): return n
x = y = n
while True:
x = eval(''.join(bin(int(digit))[2:] for digit in str(x)))
y = eval(''.join(bin(int(digit))[2:] for digit in str(y)))
y = eval(''.join(bin(int(digit))[2:] for digit in str(y)))
f = gcd(x, n)
g = gcd(y, n)
if 1 < f < n: return f
if 1 < g < n: return g
if x == y: return None
```
2. Lucas A. Brown said

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.

```fail = 0
for n in count(2):
if n % 10**5 == 0: print fail, n, float(fail) / float(n)
f = digital_coding(n)
if f is None: fail += 1
```

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.

3. programmingpraxis said

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

4. Situxuming said

The following is my Mathematica code:

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

```dc[n_] :=
FromDigits[Flatten[IntegerDigits[#, 2] & /@ IntegerDigits[n]], 2]
```

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

```gcd[n_]:=NestWhileList[dc, n, ! (1 < GCD[#, n] < n) &]
```

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

```result[n_]:=Module[{tmp=gcd[n]},Flatten[{Rest[tmp],GCD[tmp[[-1]],n]}]]
```

In Mathematica, we get:

```In:=result

Out={69919, 54073, 2847, 2599, 5529, 2921, 333, 37}

In:=result

Out={40319, 23}
```