Factoring Integers

[ElijahJones]

I will try to introduce several methods here. There is security sensitivity to this topic but nothing we do here is likely to approach a real RSA caliber factorization method so we should'nt get visited by NSA.

[ElijahJones]

This one is going to be a little tough unless you understand how the base [MATH]a[/MATH] algorithm produces a polynomial in [MATH]a[/MATH] for every integer [MATH]N>2[/MATH]. Using the algorithm for a suitably chosen base [MATH]a[/MATH] we can obtain

 

[MATH]N=a^2+C_{1}a+C_{0}[/MATH] (1)

 

Let us assume that we can pick [MATH]a[/MATH] so that not only is this true but that at least one pair of factors of [MATH]N[/MATH] can be written as [MATH]a+r[/MATH] where [MATH]r[/MATH] is a residue modulo [MATH]a[/MATH]. Then we can also write

 

[MATH]N=(a+r_{1})(a+r_{2})[/MATH]

[MATH]N=a^2+(r_{1}+r_{2})a+r_{1}r_{2}[/MATH] (2)

 

Equating coefficients from 1 and 2 above yields the system

 

[MATH]C_{1}=r_{1}+r_{2}[/MATH]

[MATH]C_{0}=r_{1}r_{2}[/MATH]

 

The conditions are [MATH]r_{1}r_{2}<a[/MATH] and [MATH]r_{1}+r_{2}<a[/MATH]. It is needed to show that for sufficiently large [MATH]N[/MATH]with factor pairs near the square root of [MATH]N[/MATH] there always exist values for [MATH]a[/MATH] that allow this construction. If one could devise a scheme for finding these values of [MATH]a[/MATH] quickly any RSA number would be within reach. Have fun!

[ElijahJones]

Theorem If [MATH]n+1=(s+1)(m+1)[/MATH] then

 

[MATH]\sum_{i=0}^{n}a^{i}=\sum_{i=0}^{s}a^{i(m+1)}\sum_{i=0}^{m}a^{i}[/MATH]

 

for any natural number [MATH]a[/MATH].

 

Suppose that [MATH]N=\sum_{i=0}^{n}a^{i}[/MATH] where [MATH]n+1[/MATH] is composite. Then [MATH]N[/MATH] is factorable by the theorem above.

 

[MATH]N=\sum_{i=0}^{s}a^{i(m+1)}\sum_{i=0}^{m}a^{i}[/MATH]

 

Notice that the theorem establishes a correspondence between the factor pairs of [MATH]n+1[/MATH] and some subset of factor pairs of [MATH]N[/MATH]. Although the result is not generally useful I include it because of the elegance of this correspondence.

 

I define the fermat divisors of [MATH]n[/MATH] to be one less than the divisors of [MATH]n+1[/MATH]. The advantage here is that we can factor [MATH]N[/MATH] by simply factoring [MATH]n+1[/MATH] which is typically much smaller.

[zaphod]

This one is going to be a little tough unless you understand how the base [MATH]a[/MATH] algorithm produces a polynomial in [MATH]a[/MATH] for every integer [MATH]N>2[/MATH]. Using the algorithm for a suitably chosen base [MATH]a[/MATH] we can obtain

 

[MATH]N=a^2+C_{1}a+C_{0}[/MATH] (1)

 

Let us assume that we can pick [MATH]a[/MATH] so that not only is this true but that at least one pair of factors of [MATH]N[/MATH] can be written as [MATH]a+r[/MATH] where [MATH]r[/MATH] is a residue modulo [MATH]a[/MATH]. Then we can also write

 

[MATH]N=(a+r_{1})(a+r_{2})[/MATH]

[MATH]N=a^2+(r_{1}+r_{2})a+r_{1}r_{2}[/MATH] (2)

 

Equating coefficients from 1 and 2 above yields the system

 

[MATH]C_{1}=r_{1}+r_{2}[/MATH]

[MATH]C_{0}=r_{1}r_{2}[/MATH]

 

The conditions are [MATH]r_{1}r_{2}<a[/MATH] and [MATH]r_{1}+r_{2}<a[/MATH]. It is needed to show that for sufficiently large [MATH]N[/MATH]with factor pairs near the square root of [MATH]N[/MATH] there always exist values for [MATH]a[/MATH] that allow this construction. If one could devise a scheme for finding these values of [MATH]a[/MATH] quickly any RSA number would be within reach. Have fun!

 

 

could you give a numerical example that demonstrates this theorem, please? i just want to be sure that i understand it.

[ElijahJones]

Yes of course.

 

Let [MATH]N=143[/MATH] Then using base [MATH]10[/MATH]

 

[MATH]143=10^2+4*10+3[/MATH]

 

Where

 

[MATH]C_1=4[/MATH]

[MATH]C_0=3[/MATH]

 

From the theorem if the factors of [MATH]N[/MATH] are linear over base [MATH]10[/MATH] we have the invertible system

 

[MATH]4=r_1+r_2[/MATH]

[MATH]3=r_1r_2[/MATH]

 

Substitution gives

 

[MATH]4=r_1+3/r_1[/MATH]

[MATH]r_1^2-4r_1+3=0[/MATH]

 

And that we know how to solve. Notice though that in this simple example we get the answer very quickly if we realize that under these circumstances everything must be a natural number so factor [MATH]C_0=3[/MATH]. Three is prime and has only the factors one and three. It is easy to verify that one plus three equals four so that the pair [MATH](1,3)[/MATH] must be a solution to the factoring problem. The result is

 

[MATH]143=(a+r_1)(a+r_2)=(10+1)(10+3)=11*13[/MATH]

 

The questions that become important then are these.

 

1) For sufficently large natural numbers with factor pairs near the square root does such a base [MATH]a[/MATH] always exist?

 

2) Is there a straightforward method for finding these special bases given a number to be factored?

 

3) Looking at base [MATH]a[/MATH] polynomials in general are there other novel factorizations?

 

NOTE The base [MATH]a[/MATH] algorithm is the process used to find the digits of [MATH]N[/MATH] base [MATH]a[/MATH]. The coefficients of the base [MATH]a[/MATH] polynomial for [MATH]N[/MATH] are it's a-nary digits. I have more to say about this if needed. Enjoy!

[ElijahJones]

This method builds on Method 1. Suppose we have [MATH]N[/MATH] an integer we wish to factor. Use the base [MATH]a[/MATH] algorithm to obtain

 

[MATH]N=a^2+C_1a+C_0[/MATH]

 

Suppose now that [MATH]r_{1}r_{2}>a[/MATH] then we arrive at a different more general system of equations than in Method 1.

 

[MATH]C_1=r_1+r_2+t[/MATH]

[MATH]C_0=r_1r_2-at[/MATH]

 

We now have two equations in three unknowns leading to a search for [MATH]t, r_1[/MATH] or [MATH]r_2[/MATH] depending on our preference.

 

Searching for [MATH]t[/MATH] is quite straightforward. We simply check each reasonable value for [MATH]t[/MATH]. That is we pick a value for [MATH]t[/MATH] and then solve the system

 

[MATH]C_1-t=r_1+r_2[/MATH]

[MATH]C_0+at=r_1r_2[/MATH]

 

Determining bounds for [MATH]t[/MATH] requires making assumptions about the distribution of factors. Here is an algorithm for investigating this new system.

 

1) Suppose [MATH]C_1[/MATH] is small. Then it is routine to simply check [MATH]t[/MATH] from zero to [MATH]C_1-2[/MATH]

 

2) Notice that if [MATH]r_1[/MATH] and [MATH]r_2[/MATH] are residues of [MATH]a[/MATH] then [MATH]r_1r_2<(a-1)^2=a(a-2)+1[/MATH] so checking for [MATH]0<t<a-2[/MATH] completes the task if we are focusing on the equation [MATH]C_0+at=r_1r_2[/MATH]. Given the way the residues of [MATH]a[/MATH] multiply you are likely to find [MATH]t[/MATH] long before you get to [MATH]t=a-2[/MATH]. This means that the algorithm is not much worse in many cases and is often better than knowing all the primes less than the square root of [MATH]N[/MATH]. Only you don't need to know them in this algorithm [MATH]t[/MATH] is a substitute for them.

 

3) If we use one equation to eliminate one of the variables. We get

 

[MATH]C_1-t=r_1+(C_0+at)/r_1[/MATH]

[MATH]r_1^2+(t-C_1)r_1+C_0+at=0[/MATH]

 

When you solve this for [MATH]r_1[/MATH] using the quadratic formula you end up with [MATH]r_1[/MATH] as a function of [MATH]t[/MATH].

 

We could also have solved for [MATH]t[/MATH] and obtained

 

[MATH]t=(-r_1^2+C_1r-C_0)/(a+1)[/MATH]

 

 

The crucial part of even looking at this method is understanding how these systems and the attendant residues and substitutes change with [MATH]a[/MATH] for a given natural number [MATH]N[/MATH]. The prime number theorem suggests that in general it is hard to get an algorithm that will do better than if you just divided by every prime less than the square root. That said, novel ways of factoring integers may still exist undiscovered and this is something that gives RSA some pause (read their website).

[ElijahJones]

In this method we will assume that every integer can be written in the form

 

[MATH]N=az+r_0=(ax+r_1)(ay+r_2)[/MATH]

 

We consider here only the case when [MATH]a=6[/MATH] and [MATH]N[/MATH] and at least one factor pair are all congruent to one modulo six. We proceed by

 

[MATH]N=6z+1=(6x+1)(6y+1)[/MATH]

[MATH]6z=36xy+6y+6x[/MATH]

[MATH]z=6xy+y+x[/MATH]

[MATH]y=(z-x)/(6x+1)[/MATH]

 

Since [MATH]z[/MATH] is known we have reduced the size of our search area from all numbers under the square root to something nearer to the number of primes less than the square root. However just like in Method 3, [MATH]x[/MATH] is a substitute for knowledge of these primes.

 

Example: Let [MATH]N=91[/MATH]. Then

 

[MATH]91=6*15+1[/MATH]

[MATH]15=6xy+x+y[/MATH]

[MATH]y=(15-x)/(6x+1)[/MATH]

 

Starting with [MATH]x=1[/MATH] we get

 

[MATH]y=(15-1)/(6*1+1)=14/7=2[/MATH]

 

It follows that [MATH]91=(6x+1)(6y+1)=(6*1+1)(6*2+1)=7*13[/MATH]

 

And this is correct. This method leaves us alot to think about. In the end the general efficiency approaches knowledge of every prime under the square root and in many cases it is better. Enjoy!

[zaphod]

another question about method 1, if you please:

 

do you have an example where the base a is not 10?

[ElijahJones]

Well you are probably going to say I am pulling a slights of hand but there are lots. One way to get more is simply to let [MATH]a[/MATH] be whatever you want it to be greater than one.

 

Base 11

 

(11+2)(11+3)=13*14

 

Base 9 and Base 10

 

(9+2)(9+3)=(10+1)(10+2)=132

 

Suppose we did not know this we would have written

 

[MATH]132 = a^2+C_1a+C_0 = a^2+(r_1+r_2)a+r_1r_2=(a+r_1)(a+r_2)[/MATH]

 

We would look for [MATH]a[/MATH] such that [MATH]r_1r_2<a[/MATH] and [MATH]r_1+r_2<a[/MATH]. The point is we need a way of determining if such an [MATH]a[/MATH] exists for every natural number greater than three and a good algorithm for finding it if it exists.

 

Can I ask how far along you are in your math training? I don't want to be talking about ring homomorphisms and Euler's phi function if you have not been exposed to those things.

 

EJ

[zaphod]

The point is we need a way of determining if such an [MATH]a[/MATH'] exists for every natural number greater than three and a good algorithm for finding it if it exists.

 

i understand now. (or at least i think i do haha). thank you.

 

Can I ask how far along you are in your math training? I don't want to be talking about ring homomorphisms and Euler's phi function if you have not been exposed to those things.

 

i'm about halfway done with my BSc. all of my linear algebra and calculus is done, but i havent taken any abstract algebra or number theory yet other than the bits that i've read and done on my own. so, not really no.

[ElijahJones]

i'm about halfway done with my BSc. all of my linear algebra and calculus is done, but i havent taken any abstract algebra or number theory yet other than the bits that i've read and done on my own. so, not really no.

 

Nice, yeah I am in grad school now, environmental science and policy. My thesis is on modeling ecosystem change (ecological succession). Nice to meet another math major. Your profile said you like mathematical physics, any topics in particular?

[zaphod]

does it really? i'll have to change that. haha i had a man-crush on feynman for a little while, and i was really getting into physics for a little while. but i've gone back to hating it.

 

thats interesting, i had actually started my BSc in Biology (Ecology Specialization), but i couldnt stay away from math. i might finish that off as a minor, though.

[ElijahJones]

Yeah Richard is pretty sexy as a human being of any gender. To be so at ease with his own genius and apparently so free. Its too bad we all are'nt as well adjusted.