Factoring By Digital Coding
April 1, 2014
A few days ago, an announcement was made in /r/crypto of a new factoring algorithm that runs in time O(log^4 n). A paper describes the algorithm. And even better, coding for the new algorithm is simple:
1)Set m ← n.
2) Express m as a list of its decimal digits.
3) Express each decimal digit as a list of binary bits.
4) Append the individual lists of binary bits.
5) Convert the resulting list of binary bits into a decimal number. Call it d.
6) If the greatest common divisor of n and d is between 1 and n, it is a factor of n. Report the factor and halt.
7) Set m ← d and go to Step 1.
Steps 1 through 4 form the digital code of a number. For example, 88837 forms the bit-list 1 0 0 0, 1 0 0 0, 1 0 0 0, 1 1, 1 1 1, where we used commas to delineate the decimal digits. That bit-list is 69919 in decimal, which is the digital code of 88837. To find a factor of 88837, compute successive digital codes until a gcd is greater than 1; the chain runs 88837, 69919, 54073, 2847, 2599, 5529, 2921, 333, at which point gcd(88837, 333) = 37 and we have found a factor: 88837 = 74 × 37. Factoring 96577 is even faster: the digital code of 96577 is 40319, and gcd(96577, 40319) = 23, which is a factor of 96577 = 13 × 17 × 19 × 23. But trying to factor 65059 = 17 × 43 × 89 causes an infinite loop. The paper gives a heuristic solution to that problem, but we’ll stop there and accept that sometimes a factorization fails.
Your task is to write a function that factors by digital coding. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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}