# Another Base a Factorization Method

• Playdo
In summary, the conversation discusses a method that uses discrete binary operations to solve equations involving integer division. It is shown that this method is useful for performing long calculations with integer division. The conversation also demonstrates a quadratic template for a natural number N and discusses how it can be further simplified. Additionally, the conversation explores the relationship between different equations and suggests using specific values for a to make the process more efficient. It is also mentioned that this method may not be useful for numbers that are not coprime and that it may be more beneficial to consider specific cases for better results.
Playdo
This method utilizes discrete binary operations, in particular notice that.

(I1) $$Div(x+y+z,a)=Div(x,a)+Div(y,a)+Div(z,a)+\{0,1,2\}$$

This means that for one of the elements of the included set {0,1,2} the equation is true. This notation is quite useful for carrying out long calculations using integer division as will be apparent in a moment.

Also note that

(I2) $$Div(xy,a) \leq yDiv(x,a) \leq xDiv(y,a) if y>x$$

Now we first start with a type of quadratic template for a natural number N, that is

(1) $$N=XY \rightarrow az+t =(ax+s)(ay+r)$$

Notice we do not require N and a coprime. This leads immediately to

(2) $$z = axy+ sy+rx + Div(rs,a)$$

This is because $t=Mod(rs,a)$ was removed after expanding the product XY.

Equation 2 can be further dealt with by noting that

(3) $$Mod(z,a) = Mod(sy+rx+Div(rs,a),a)$$

(4) $$Div(z,a) = xy + Div(sy+rx+Div(rs,a)) = xy + Div(sy)+Div(rx)+Div(Div(rs,a),a) + \{0,1,2\}$$

Equation four can be categorized depeending on the relationships of s to y and r to x. Notice that $Div(Div(rs,a))<Div(a-2,a) = 0$ therefore this term is obliterated. If we restrict x and y to be less than a then $Div(sy,a)<a-2$. So by dividing (4) by a again we obtain

(5) $$Div(Div(z,a),a) = Div(xy+Div(sy)+Div(rx)+\{0,1,2\},a)$$
$$= Div(xy,a)+Div(Div(sy,a))+Div(Div(rx,a))+Div(\{0,1,2\},a)+\{0,1,2,3\}$$

Or in the sixth step

(6) $$Div(Div(z,a),a) = Div(xy,a) + \{0,1,2,3\}$$

Ah the beauty of the seventh step!

(7) $$Div(xy,a) = Div(Div(z,a),a)-\{0,1,2,3\}$$

After this we recognize that in short order we know a key ingredient if you will of xy since the division algorithm shows us that

(8) $$xy = Div(xy,a)+Mod(xy,a)$$

But of course we know that Mod(xy,a) is greater than zero and less than a, this is not as impressive as we wish it to be. if N and a are coprime we reduce the residues to be searched to the reduced residue system modulo a. But perhaps by taking the modulus of Equation four we can obtain a better estimate.

(9) $$Mod(Div(z,a),a) = Mod(xy,a) + Mod(Div(sy+rx+Div(rs,a)),a)$$
$$= Mod(xy,a) + Mod(Div(sy),a)+Mod(Div(rx),a)+Mod(\{0,1,2\},a)$$

The modulus of the set {0,1,2} is clearly equal to itself. The modulos of the terms containg sy and rx will be harder to come by. In fact right now I do not see a way past the terms of the form [itex]Mod(Div(sy,a))[/tex].

Last edited:
In fact right now I do not see a way past the terms of the form [itex]Mod(Div(sy,a))[/tex]

But what if we study the relationship

(12) $$Mod(Div(sy,a)+Div(rx,a),a)=Div(Mod(sy,a),a)+(Div(Mod(rx,a),a)$$

How are these two expressions different? Suppose we have

(13) $$Div(sy,a) \leq sDiv(y,a)$$

Where we have restricted y to be less than a. Then

(14) $$Mod(Div(sy,a),a) \leq Mod(sDiv(y,a),a)$$
$$= Mod(s,a)Mod(Div(y,a),a)=Mod(s,a)*0$$

There are a lot of equations in this derivation so we will have to work some simple examples just to get a better feel for the whole thing but if this is right we can pick up from (9) above and right

(15) $$Mod(Div(z,a),a) -\{0,1,2\} = Mod(xy,a)$$

We have extraceted xy from the equation (2) above and arrived at a set of five systems of two independent equations in four unknowns. Namely the systems

(S1)

(S1:1)$$xy = Div(Div,z),a) +Mod(Div(z,a),a)-\{0,1,2,3,4,5\}$$
(S1:2)$$z = axy+sy+rx+Div(rs,a)$$

This would appear daunting still because r and s are unknown residues of a. However if we pick a so that the reduced residue system has special properties some of the apparent difficulty vanishes. Suppose a is prime, then every element less than a is in the reduced residue system which is an abelian group under multiplication modulo a. Is this useful?

If we can find x and y from the five equations (S1:1) we can rewrite (S1:2) as (S1:2:E1) the E means evolved from,

(S1:2:E1) $$N = az+t = a^2xy+asy+arx + rs$$

And then

(S1:2:E1:E1) or more simply (S1:2:1:1) is

(S1:2:1:1) $$r = \frac{az-a^2xy - asy}{ax+s}$$

If as I have discussed in other threads the (r,s,Div(rs,a)) triples are esay to find and the r.r.s. modulo a is relatively small in size N falls open like a roasted pistachio.

Much of the arithmetic here is predicated on the notion that x and y are small. I want to take some time to look at this using base 6 which has a very nice r.r.s. and the using the larger polynomials discussed in other threads. Because what appears to be happening here is the interplay of two processes that have ot be iterated. There is a top-side iteration represented by xy and a bottom-side iteration represented by rs and the residue system modulo a. Finding the best combination of techniques to minimize the interval of iteration from top and bottom may be worth looking into.

I see little benefit to considering cases where N and a are not coprime, although the calculation above was carried out under that premise. The reason is that if N and a are not coprime, then some zero divisor of a divides N, we can factor a to find one divisor of N. This is useless for RSA type numbers composed of only two very larger prime factors.

Last edited:

Thank you for sharing this alternative factorization method. It seems to utilize a lot of discrete binary operations and equations to break down a natural number N into its factors. I can see how this method could be useful for carrying out long calculations using integer division. However, the notation and equations may be a bit complex for those not familiar with discrete math or number theory. It would be helpful to provide some examples or further explanation of the steps involved in this method. Also, I'm curious about the limitations of this method and if it is more efficient or accurate compared to other factorization methods. Overall, it's interesting to see a different approach to factorization and I appreciate you sharing it.

## 1. What is "Another Base a Factorization Method"?

"Another Base a Factorization Method" is a mathematical approach to finding the factors of a given number. It involves using a different base number system, such as base 2 or base 3, to express the number in a different way and make it easier to identify its factors.

## 2. How does "Another Base a Factorization Method" work?

This method works by converting the given number into a different base number system and then using algebraic methods to factor it. This can involve techniques such as factoring by grouping or using the difference of squares formula. The factors found in the alternate base can then be translated back to the original base to get the final result.

## 3. What are the advantages of using "Another Base a Factorization Method"?

One advantage of this method is that it can be more efficient and organized than other traditional factoring methods. It can also be helpful for factoring large numbers that may be difficult to factor using other methods. Additionally, this method can provide a different perspective and approach to factoring, which can be beneficial for students learning about factorization.

## 4. Are there any limitations to "Another Base a Factorization Method"?

One limitation of this method is that it may not always work for every number. Some numbers may not have easily identifiable factors in alternate base number systems, making it difficult to use this method. Additionally, it may not be as straightforward for those who are not familiar with different base number systems.

## 5. How is "Another Base a Factorization Method" used in real-world applications?

This method can be used in various fields such as cryptography, computer science, and number theory. It can be used to factor large numbers in encryption algorithms, to optimize computer algorithms, and to study patterns and relationships between numbers. It can also be used in problem-solving and mathematical research.

• Quantum Physics
Replies
1
Views
744
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Linear and Abstract Algebra
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Precalculus Mathematics Homework Help
Replies
17
Views
664
• Linear and Abstract Algebra
Replies
4
Views
3K
• Electromagnetism
Replies
4
Views
973
• Linear and Abstract Algebra
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
4
Views
1K
• Linear and Abstract Algebra
Replies
3
Views
2K