[Of course some of you will let me know if we need numerical examples or if something just does not make sense, or if it is very similar to what somebody else has already done, and I appreciate that.](adsbygoogle = window.adsbygoogle || []).push({});

Suppose we have a reducible polynomial over the natural numbers (zero include) such that

[tex] \sum^n_{i=0}\alpha_{i}a_{i}=\sum^s_{i=0}\beta_{i}a_{i}\sum^m_{i=0}\gamma_{i}a_{i}[/tex]

By substituting natural number values for [itex]a[/itex] on the left side we obtain a sequence of natural numbers. Buy substituting the same value on the right we find one factorization of the number formed by substituting on the left.

This equation acts as a map between factor pairs of the generated sequence. If we then think of our normal way of writing the equation as the polynomial base a of the number base ten found by simplifying the left hand side, we realize we can do the same for every element of the sequence. That is if we wanted to factor a very large number with polynomial expansion given by the left hand side, we could simply substitute for a, say two, then simplify that number base ten which would produce a much smaller number to be factored that has at least one factor pair that we can map back to a factor pair of the desired number. Suppose that new number was still too large. Do the same thing over and over until you arrive at a number that is clearly easy to factor and work your way back up.

The problem with daisy chaining the algorithm is there is no way of knowing which factor pair corresponds to the upward mapped pair, so we may have to search through all factors pairs of each rung below it.

A hinderance of even a single move from base [itex]a[/itex] to base two and then simplification in a base [itex]b[/itex] is that you need a reducible polynomial that evaluates to N base [itex]a[/itex] or else the assumptions do not hold.

Notice that the typical base [itex]a[/itex] expansion algorithm does not always give a reducible polynomial in [itex]a[/itex]. That I think is the question that all of this hinges on, is it easy or hard to work through the linear space of base a polynomials that evaluate to N. Some of this stuff is in the other thread. But if we have two numbers, a factor pair of N that multiply without carrying base ten then N will have a base ten expansion that is reducible as a polynomial if we replace ten with a generic natural variable [itex]a[/itex].

Every natural number having a reducible base [itex]a[/itex] expansion can be tackled using the method we are talking about here. A way that I have thought to try to get around the loss of information due to carrying in the multiplication process is to try to understand the density of reducible base [itex]a[/itex] expansions for a given natural number N.

Is it true that there must be a base [itex]a[/itex] less than N such that the base [itex]a[/itex] expansion of N is a reducible polynomial in [itex]a[/itex] as a variable?

Some folks have trouble with the notion of thinking of something as constant one moment and then variable the next, but don't we do something similar to that with partial differentiation to obatin the derivative?

Note: Notice that the polynomial does not need to offer a complete factorization of N to be useful and in fact it would have to be of degree no less than the number of distinct prime factors (up to mutiplicity) of N. We can get started very well using polynomials that allow only two irreducible factors base a.

*****************************************************

Update on my own intentions. I am thinking about pursuing a Phd now again in pure math. I would like to study elementary number theory. Also to focus on Chaitin's Omega Number. Apparently he used an Diophantine equation to discover the halting probability of the universal Turing machine. Which the number itself is amazing, though not really embraced I guess by mainstream computer science or math. A number so complex you cannot write it down!

It occured to me that all of the problems I have ever been deeply interested in have been in elementary number theory or it's applications. I don't know though, I'm also preparing for the actuarial exams. But being a professor and working on number theory could work for me. I feel a little like Dorothy. I did not like the culture in my little part of the math world so I ran away from home and found out that teaching and being around others who are freakishly inquisitive has alot to say for itself. My apologies to the universe, to the community if needs be.

******************************************************

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Factorization Algorithm II

Loading...

Similar Threads - Factorization Algorithm | Date |
---|---|

Integer Factorization Algorithm | Apr 14, 2008 |

The limit of a factoring algorithm | Nov 24, 2007 |

Construct for a Base a Factorization Algorithm | Oct 22, 2006 |

A Factorization Algorithm | Jun 30, 2006 |

Need help in factoring algorithms | Jul 12, 2005 |

**Physics Forums - The Fusion of Science and Community**