(I got this material from a nice article by Arthur Benjamin here.)
Conway suggested the following trick to determine if a number is divisible by each of the following:
2,3,5,7,11,17,19,31
Note that
\( 152=2^3\times 19\)
\(153 =3^2 \times 17\)
\(154=2 \times 7 \times 11\)
\(155=5 \times 31\)
\(156=2^2 \times 13 \)
Here is the Div trick:
a) Input N
b) Divide N by 150 and note the remainder. So
N=150q+r
r=N-150q
Subtract q from r a few times:
Note that
r-q = N-150q-q = N-151q
r-2q=N-152q
AH HA!- if 19 divides r-2q then 19 divides N. So divide r-2q by 19. (Note that r-2q is much smaller than N. Smaller enough to make this technique feasible? That is the question!)
r-3q=N-153q.
AH HA!- if 17 divides r-3q then 17 divides N. So Divide r-3q by 17.
r-4q=N-154q
AH HA- if 11 divides r-4q then 7 divides N. So Divide r-4q by7.
r-5q=N-155q
AH HA- if 31 divides r-5q then 31 divides N. So Divide r-5q by 31.
r-6q=N-156q
AH HA- if 13 divides r-6q then 13 divides N. So Divide r-6q by 13.
Complexity with 1 division, 6 subtractions and 6 divisions of small numbers (r\le 150 and q\le N/150)
you find out the divisibility by 7,13,17,19,31. For 2,3,5,11 there are well known tricks to use. OR you can test those as well by doing (for example) dividing r-4q=r-154 by 11.
Some Points
1) Is this method faster than just dividing N by the numbers (and using tricks for 2,3,5,11)? You would need to get into addition being faster than division, and look at the size of the numbers.
2) Is this method practical? For hand calculation YES. For computers it would be easy to code up but the main question of this post: is it better than just dividing N by numbers.
3) Are there larger runs of numbers that pick up more divisors? Yes. We present one. The order will look funny but we explain it later.
\(2000=2^4 \times 5^3 \) (you could skip this one, though dividing by 2000 is easier than by 2001)
\(2001=23\times 29\times 3\) (would divide N-2q by both 23 and 29)
\(2002=7\times 11\times 13\times 2\)
\(1998=37\times 54\)
\(2006=17\times 29\times 2\)
\(2010=67\times 30\)
\(2014=19\times 53\times 2\)
\(2013=61\times 33\)
\(2015=31\times 65\)
\(2009=41\times 49\)
\(2021=43\times 47\)
The order was suggested by Conway so that algorithm at every step adds or subtracts one of q, 2q, 4q, 6q, 8q, 12q. So after you get q you can compute these values.
I leave it to the reader to count the number of divisions, subtractions, and size of the numbers involved.
4) For cracking RSA this technique is useless since RSA uses numbers of the form pq where p and q are large primes. For factoring randomly generated numbers I would be curious if this method is better than just dividing by numbers.
5) Project: find other sequences like those above that cover more prime factors.
Note also that this involves first dividing $N$ (the number to be factored) by a fixed number. From my glancing at Wikipedia, it looks like
ReplyDeletemany
integer factorization methods work by computing things mod $N$, instead.
Also, note that $150 = 2 \cdot 3 \cdot 5^2$, which is to say, small prime numbers. This reminds me (admittedly tangentially) of something I tried (which didn't work):
I was trying to reduce factoring to graph isomorphism. My thinking was: suppose we're trying to factor $N$. If $N = ab$, then $N \cong ab (mod p_i)$, for any primes $p_i$. (This is true, but turns out to not be useful; see below...)
I then tried to make a gadget to enforce this, using a weird cross between the reduction from SAT to CLIQUE, and the Chinese remainder theorem. (Code is at https://github.com/joshtburdick/misc/blob/master/cs/graph_iso_and_factoring/graph_fact.py .) I'm not sure the gadget guaranteed this, but that's moot, because:
The fly in the ointment was that, mod $M$, *anything* relatively prime to $M$ is a factor of $N$. So there are $\phi(M)$ factorizations mod $M$, but only a handful of those are actual integer solutions.
So, yes, this is a non-working idea. But I'm wondering if there is a way to patch it into something useful.
I tried tweaking this slightly, but modifying Fermat's "difference of squares" method, to factor some N. Again, start by picking small primes $p_i$, and let $m = \prod_i p_i$.
ReplyDeleteFollowing Fermat's method, you then look for $a, b$ such that $a^2 - b^2 = N (mod m)$. If it's true for $m$, then it's true for lots of $p_i$. So, since $N = (a+b)(a-b)$, hopefully a+b, a-b, or b-a will share a common factor with $N$. (As far as I can tell, this is basically like the
last step (here, step 6) of the Quadratic Sieve, which has similarities to Fermat's method.)
As a toy example, suppose you pick m = 7*11, and you're trying to factor 15. (As I said, toy example...)
We might find a=3, b=62: note that 3^2 - 62^2 = -3835, and -3835 mod 77 is 15 .
3-62 is congruent to -59, or 18, mod 77. And GCD(18, 15) = 3. In this case, we found a factor. Woot!
However, we might not be so lucky. If we find a=18 and b=34, then
18^2 - 34^2 = -832, and -832 mod 77 is 15.
a+b=52, a-b=61, and b-a=16. GCD(any of those, 15) = 1, so we didn't find a factor. Sadness.
I did a bit of sampling (in this Colab notebook; I used Gemini some) to see how often this yielded a nontrivial factor. It didn't always, but it was more than a fraction of 1/N of the time.
To reiterate: I have _no idea_ of an efficient way of finding $a$ and $b$ which work. However, if one could find them efficiently, then that might _sometimes_ yield a factor of $N$. (And I'm not sure how often.) So, best case, this may be reducing factoring "sideways", to an equally-difficult problem.
My questions:
1. Is this more similar to something besides Fermat's factoring method? (To me, it's reminiscent of the Quadratic Sieve; but that method uses mod-N arithmetic.)
2. If not, can it be modified to something else interesting?