Friday, January 25, 2008

 

More explanation on factoring congruences

I realized that maybe I might help things by explaining more in detail what the factoring congruences mean and what some of my statements in presenting them means, so this post is for that and it shouldn't be too long.

For reference, for a composite T that you want to factor, so you want f_1 and f_2 where f_1*f_2 = T, 75% of the time (and I'll explain that below) for a prime p of your choice you can find f_1 mod p and f_2 mod p with the following relations:

f_1 = ak mod p

and

f_2 = a^{-1}(1 + a^2)k mod p

where

k^2 = (a^2+1)^{-1}(T) mod p.

So you have relations for f_1 mod p and f_2 mod p, but you have these two other variables which are 'a' and k, where you want ANY integer that will work such that

(a^2+1)^{-1}(T) is a residue modulo p.

For instance, with p=17, and T = 15 mod 17, you'd have

k^2 = (a^2+1)^{-1}(15) mod 17

and an 'a' that fits is a=1. As, then k^2 = 2^{-1} (15) mod 17 = 9(15) mod 17, which is a quadratic residue as it's 16 mod 17, so k=4 mod 17 will work!

It turns out that only 3 a's will work: 1, 5 and 7

So the a's are ANY integers that will fit so that you get a k, as, for instance, if you try an 'a' that gives you k^2 = 3 mod 17, you know that isn't a valid one as 3 is not a quadratic residue modulo 17, so there is no integer answer for k.

Now if you try to factor 15 with these congruences I think are so great, you get a surprise! None of them will factor it non-trivially.

That goes back to that 75% of the time they will work.

To get a bigger picture consider 15 + 17(5), which is 100. It has 5 combinations of factors:

2(50), 4(25), 5(20), 10(10), and 100(1)

where notice the trivial factorization gets one count.

But you have only three values for the a's, and they will give you residues modulo 17 for the following factors for 100:

2(50), 4(25), and 100(1)

Notice though that with 2(50), f_1 = 2, means that f_1 = -15 mod 17, and f_2 = 50, gives you f_2 = -1 mod 17.

So those are the answers for (-15)(-1), and if you go to 100, f_1 = 100, you have

100 = 15 mod 17, so f_2 = 1, so it's 1 mod 17.

So those are duplicates, and one of the a's is not represented.

There are 5 possible combinations that you can have for 15 + 17c modulo 17, but the factoring congruences will give you only 3.

So they will give you 3 out of the 5 which is 60%, under the maximum of 75%, but that's a probability for you, not all cases will give it exactly.

If you're curious, try out that result!

For 15 + 17c, for ANY integer c, you will find that when factored there are only 5 combinations of factors modulo 17 that you can get along with their negations.

They are: {4,8}, {6,11}, {4,2} given by the factoring congruences and {5,3} and {10,10} not given by them.

The negations then are: {-13, -9}, {-11, -6}. {-13. -15}. and {-12. -14} and {-7, -7}.

So to rec-cap the factoring congruences will give you residues modulo T for the factors of a composite T, but they can miss some combinations as they work on average 75% of the time, where for my example with composites of the form 15 + 17c, modulo 17, I found they only work for 60% of the cases, as the probability means you can find cases above or below that 75%.

But notice they do work.

Factoring with them practically is another subject, which I've addressed in other posts.





<< Home

This page is powered by Blogger. Isn't yours?