A method for factorization

smslca

I like to give a method for factorization.

Below method is not an efficient method , but it is a method to factorize.

I dont know it already exist or not , which mean I have searched for this process on internet , But I did not find this method. So , may be I missed the page where this method already is , or it did not exists.


P-n method:

This method goes around the fact that , Any number P can be written as p - n + n ; n is any number . Here p is an odd number and is not a prime number.

If p0 is the given number. then
if p0 = p1 * p2 ; here p1 < p2
p0 - n = x1 * x2; here x1 < x2
then p0 = (p0 - n ) + n
==> p0 = ( x1 * x2 ) + ( |p1 - x1| * x2 ) - ( ( |p1 - x1| * x2 ) - n ) ;
or p0 = ( x1 * x2 ) - ( |p1 - x1| * x2 ) + ( ( |p1 - x1| * x2 ) + n ) ;
assuming |p1-x1| is the least difference .

Total no.of.loops = 2 * 2 * |p1 - x1| * divisor arrangements

divisor arrangements is explained below.

p-1 method. (later explained p-n method)

---

for example consider p-1 method explained with an example .
If given p is odd then p-1 is always an even number .
Let P0 = 919829 = 587 * 1567, then p-1 = 919828 = 2 * 2 * 229957
So , here we have to arrange the p-1 as the product of two divisors . like divisors_arrangement = 2*459914 or 4*229957
*** This divisor arrangement is important because we dont know, for which arrangement we will get an answer.
Here I am taking p-1 = 4*229957
As we know that p = (p-1) + 1 ;
so p = (4*229957) + 1
==> p = (4*229957) + (583 * 229927) - ( (583 * 229927) -1)
==> p = (4 * 229957) + (583 *229927) - 134064930
==> p = (229957 * 587 ) - 134064930
Here this 134064930 is exactly divisible by 587 as 134064930 = 587 * 228390
so p = (229957 * 587 ) - ( 587 * 228390)
==> p = (587 * (229957 - 228390))
==> p = (587 * 1567)

---

which is the required solution.

Here it is inefficient because it requires 587 - 4 no .of loops to factorize .
i.e . if a number n = n1 * n2 ,if n1 < n2 , and n-1 = (2^a0) * n3 , then it requires ( n1 - (2^a0) ) = lowest factor of p - lowest factor of (p-1) loops to factorize.
It is not necessarily to be difference of lowest factors. It may be "largest factor of p - largest factor of (p-1)) , if the difference is negative modulus of the number is the required loops , the least of the difference is the minimum no.of loops we are going to run .

also since there may be |negative difference|< +ve difference , we are going to check
total loops = (2 * the least difference ) * no.of.arrangements of divisors

Another cause for inefficiency is the no.of.arrangement of p-1 factors as the product of two divisors.
if there a "h" ways for the arrangement then the total no.of loops to factorize is = [ h * ( n1 - (2^a0) ) ]

The no.of.loops can be further decrease by , factorizing 229957. It can be done by taking p1 = 229957 and calculate p1 -1 and then proceeding the same steps as done above.
this must be continued until we get pn-1 = (2^an)*prime number , at some point of n.
Here 229957 can be factorized into = 7*7*13*19*19
for the above number 919829 the total number of loops decreased from 583 to 433 loops .

p-n method:

---

based on p0 = (p0 - n ) + n
The problem in above method is we have to do approximately the factor<sqrt(p) loops to factorize .
since the above number can be factorized even further we have decreased the no.of .loops .
But If numbers like 33250423 = 4363 * 7621= p0 has p0-1 = 6 * 5541737 . where 5541737 is a prime number then the total no.of .loops
to be run = 4363 - 6 = 4358 loops .
So replace (no.of.digits of p0 )/2 of p from left as zeros . i.e do p0 - 423 = 33250000 , now factorize this number using the same method for which you will get one of its divisors as 4375 , which means 33250000 = 4375 * 7600 ;
so the loops to be run = 2* |4363 - 4375 | * no.of.divisors arrangements = (12 * no.of.divisors arrangements ) loops.

Here also there exits an inefficiency ,
1. as the no.of.factors of p0 - n increases the no.of .ways of divisors arrangement increases. There by increasing the no.of.loops.
2. It is sure that by replacing (no.of.digits of p0 )/2 zeros will get one of the divisor of p0-n nearest to the divisor of p0 .
But I am not sure about the exact no.of zeros that has to be replaced . because,
---the number 694,891,321,868,591 = 15487811 * 44866981 will have the nearest divisor when no.of.zeros to be replaced is,
( (no.of.digits of p0 )/2 - 1 ) , i.e for 694,891,321,000,000 having divisor 15446320 . giving a difference of 41491 ;
---and for number 49976497 = 6343 * 7879 ; we will get minimum when zeros = ( (no.of.digits of p0 )/2 - 1 )
i.e ., at 49976000 have divisor 6247 , giving a difference of 91;

FoxT

I dont understand it I'm afraid....

If p0 is the given number. then
if p0 = p1 * p2 ; here p1 < p2
p0 - n = x1 * x2; here x1 < x2 -> what about say 18-5 ?

do you mean
f p0 is the given number. then
if p0 = p1 * p2 ; here p1 < p2
AND
p0 - n = x1 * x2; here x1 < x2 ?

But, how would you know that?


Also I don't understand what you mean by 'least difference' ?

smslca

FoxT wrote: »

I dont understand it I'm afraid....

If p0 is the given number. then
if p0 = p1 * p2 ; here p1 < p2
p0 - n = x1 * x2; here x1 < x2 -> what about say 18-5 ?

I said p0 must be an odd number. As I said in p0-n method replace (no.of.digits of p0)/2 by zeros from left to right of p0 to get p0-n .

ok lets take p0 = 18 =2*9
here least divisor = 2
then take p0-5 = 18-5 = 13 , which is a prime number
==> p0-5 = 1 * 13
Here the least difference is 2-1 = 1 and all the other differences will give greater than 1 .

---

lets check do we get answer at first loop. Here the problem is , since we do not know the factors of p0 = 18 , we dont know the least difference before doing loops. It is just for explanation purpose .

we must start any loops with 1 and then increase by 1 there on if we did not got an answer.

so we can write p0 = 18 = (p0-5) + 5
===> p0 = (1*13) + 5
===> p0 = (1*13) + (1 * 13) - ((1*13) -5) = (1*13) + 5
===> p0 = 13*(2) - 8
here 8 will be exacly divisible by 2 . and 8/2 = 4
===> p0 = (13*2) - (2*4)
===> p0 = (13-4) * 2
===> p0 = 9 *2 .
finally we got the answer.

here we have replaced 5 with (1 * 13) - ((1*13) -5) . If we do not get an answer with that , then try replacing 5 with (2 * 13) - ((2*13) -5) and so on.