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!

About these ads

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[1]:=result[88837]
    
    Out[1]={69919, 54073, 2847, 2599, 5529, 2921, 333, 37}
    
    In[2]:=result[96577]
    
    Out[2]={40319, 23}
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 609 other followers

%d bloggers like this: