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!
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 NoneWhile 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 += 1I 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:
result[n_]:=Module[{tmp=gcd[n]},Flatten[{Rest[tmp],GCD[tmp[[-1]],n]}]]In Mathematica, we get:
In[1]:=result[88837] Out[1]={69919, 54073, 2847, 2599, 5529, 2921, 333, 37} In[2]:=result[96577] Out[2]={40319, 23}