A Composite Number Containing Only Two Primes

[Anamitra]

Let N be composite number containing only two primes a and b
That is,
N=a*b, where a and b are primes
Factorizing N[even on a computer] is an impossible task if N is very large,for example if it has 400 digits.
But we can eliminate a huge number of divisors by the following rules:
1.If n does not divide N exactly then the product n*[composite number] does not divide N
2 Any composite number less than N/2 should be excluded from the list of divisors.

[Rule (2) is of a more general nature]
Does this process of de-selection in any way simplify the task of the person on the computer, considering the fact that there are only about 3.2 * 10^7 seconds in a full year?
I have a similar posting on the Usenet: sci.math.research.
Title:Factoring Composite Numbers[Containing a Pair of Primes Only]
Date of Posting:10th June,2011
Current link:https://groups.google.com/group/sci.math.research/topics?hl=en&lnk

 

[Anamitra]

Analytical Version of the Problem
Let N=A*B, where A,B are primes
Let: $${N}{=}{c}_{p-1}{x}^{p-1}{+}{c}_{p-2}{x}^{p-2}{+}{...}{c}_{1}{x}{+}{c}_{0}$$ ------------------ (1)
$${A}{=}{a}_{m-1}{x}^{m-1}{+}{a}_{m-2}{x}^{m-2}{+}{...}{a}_{1}{x}{+}{a}_{0}$$ ----------------- (2)
$${B}{=}{b}_{n-1}{x}^{n-1}{+}{b}_{n-2}{x}^{n-2}{+}{...}{b}_{1}{x}{+}{b}_{0}$$ --------------- (3)


X is the base of the number system used
Digits of N: $${c}_{p-1}{c}_{p-2}{...}{c}_{1}{c}_{0}$$
The above digits are known to us
Digits of A: $${a}_{m-1}{a}_{m-2}{...}{a}_{1}{a}_{0}$$
Digits of B: $${b}_{n-1}{b}_{n-2}{...}{b}_{1}{b}_{0}$$
The digits of A and B are not known to us. The main problem is that the individual values of m and n are not known to us though we know p=m+n-1
In the relation N=AB we may substitute the expressions for N ,A and B [ie, expressions:(1),(2) and (3)]
If m-1 is allowed to run from 0 to p-1 [ie m runs from 1 to p] we have “p” relations of the type
N=AB
In each of the “p” relations[N=AB] we can multiply the expressions on the RHS and then equate the resulting coefficients on either side[the coefficients and powers on the LHS are known to us.
We have “p” equations[ordinary non-linear equations of degree 2] and “p” unknowns in each set
There are “p” such sets[since m runs from 1 to p]
The one that produces positive integral values for all ai and bii should be accepted. Only two sets[corresponding to N=AB and N=BA] will have this property since N is the product of two primes. We may increase the base of the number system to reduce the number of equations in each set and also the number of sets of equations.
Additional Points
1. Instead of running m from 1 to p it would be convenient to run m from 1 to (p+1)/2, rounded to the integral value on the higher side, if p+1 is an odd num.
2. If N itself were a prime no set should produce positive integral values for all ai and bi simultaneously

 

[Anamitra]

Complications to Consider:

Referring to the previous posting we may have equations like
$${\Sigma}{a}_{i}{b}_{j}{=}{p}_{k}$$
[i+j=k]
The summation may extend over a large number of terms. If ai and bj are themselves integers less than 10[suppose we are using base =10] the summation may result in a large number greater than pk which is less than 10.
Actually I had missed out the effect of " carry" in the last posting.
In this consideration we have to accept fractional values of ai and bi subject to the condition that A and B are simultaneously integers.

If the fractions ai and bi are constrained to contain powers of 2 and or 5 in the denominator[when ever these quantities are fractional] the situation would improve.
ai or bi=1/k(i),
K(i) contains powers of 5 or 2 and k(i)<10^i
This may improve the situation

 

[Anamitra]

An Interesting Observation::
Problem: We have to factorize a natural which is the product of a pair of primes only, that is,
N=A*B where A and B are primes.

We consider a known polynomial expression in x which is of odd degree. It can be factorized into a pair of factors.All coefficients involved in the above expressions/functions are integers which may be positive or negative[or zero for some]. These integers are known to us.

$${x}^{n}{+}{a}_{n-1}{x}^{n-1}{+}{a}_{n-2}{x}^{n-2}{+}{...}{+}{a}_{1}{x}{+}{a}_{0}$$
$${=}{(}{x}^{p}{+}{b}_{p-1}{x}^{p-1}{+}{b}_{p-2}{x}^{p-2}{+}{...}{+}{b}_{1}{x}{+}{b}_{0}{)} {(}{x}^{q}{+}{c}_{q-1}{x}^{q-1}{+}{c}_{q-2}{x}^{q-2}{+}{...}{+}{c}_{1}{x}{+}{c}_{0}{)}$$ -------------- (1)
["n" is an odd number; p+q=n;The above relation is an identity]
Let us write:
$${x}^{n}{+}{a}_{n-1}{x}^{n-1}{+}{a}_{n-2}{x}^{n-2}{+}{...}{+}{a}_{1}{x}{+}{a}_{0}{=}{N}$$ -------------- (2)
and solve x in the above equation ie,equation(2).

If the value of "x"turns out to be an integer[that is, the above equation has an integral roots]our work is done . We simply put this value into the RHS of (1)
Since the equation is of odd degree and we know that complex roots and irrational roots occur in conjugate pairs, the equation we are considering must have at least one rational root.
If the exact fractional form of this rational root [of the form r/s,[where r,s are integers] is known to us we may multiply both sides of (2) by the highest power of "s" and look for the values A and B.
But finding the exact fractional form may be a frustrating task even in the case of cubic equations .

[Relation (1) is an identity]

 

[Anamitra]

A Simple Illustration
Let me try factorizing N=122 using the above technique:
The expression/identity chosen is
$${x}^{3}{-}{15x}{-}{4}{=}{(}{x}{-}{4}{)}{(}{x}^{2}{+}{4}{x}{+}{1}{)}$$----------(1)
We write,
$${x}^{3}{-}{15x}{-}{4}{=}{122}$$ -------------- (2)
And solve the above equation by Cardan’s Method[or otherwise].
We get X=6 [Fortunately, we have an integral solution here]
Putting this value into the RHS of (1) we get
N=2* 61

 

[Anamitra]

A simple Gadget to Work Out the Elimination of Divisors[Suggested in the first posting]:

We take a large circular loop which small enough to be kept on a large table in some room.
Let the circumference be some multiple of 7 cm.We assume that 7 does not divide N[=A*B,where A and B are primes]We take spots on this loop which are equally spaced at distance 7 cm from each other[and starting from some origin O on the loop].. These 7 spots are actually eliminating all multiples of 7 that is ,N/7 which is approximately equal to 10^400/7 divisors, which itself is a huge number.Now we take another prime number say 11. We start from a different origin 77 cm from the first one,that is the same origin.From the new origin we start in steps of 11 cm. We mark the new points till we come back to the new origin[may be after a few loops].Again we have eliminated a huge set of points . I mean to say the multiples of 11[This is less than 10^400/11 because of the common multiples of 7 and 11 that is 77. Nevertheless the number is very large]. By taking different prime numbers[or other numbers with the exception of one]]that do not divide N we may keep on eliminating divisors [without actually dividing N by each divisor]
Now ,the entire set of points from one to N are simply discrete points on the loop.And we go on eliminating unnecessary points/divisors by the method described.
Is it possible to speed of the "search process" by this method coupled with other techniques--say statistical ones[or ones based on the microprocessor]?

[N is assumed to have four hundred digits]

 

[Anamitra]

Complications
We take a large circular loop which small enough to be kept on a large table in some room.
Let the circumference be some multiple of 7 cm[in this example we take circumference=700cm].We assume that 7 does not divide N[=A*B, where A and B are primes]We mark points on this loop which are equally spaced at distance 7 cm from each other[and starting from some origin O on the loop].. These 7 spots are actually eliminating all multiples of 7 that is ,N/7 which is approximately equal to 10^400/7 divisors, which itself is a huge number.
We start from the same origin again , this time in steps of 11cm.The first point after the origin after a full loop will be 704cm from start and now it is at a distance of 4cm from the origin . So the number 4 is in consideration now together with eleven and all their multiples get eliminated[steps of 4cm have to marked now along with 11]. Suppose we took 71.The first point after a full loop is 61 cm ahead of the origin[71*9+61=700]. If 61 does not divide N all multiples of 61 get excluded along with 7,11 and 4 .Of course we have to mark all steps of 61[ and 4].

But this method is quite defective since 700n+r could denote a very large prime number. The previous method also has similar defects

Revised Method

A Better Method would be to take several wheels whose circumferences are multiples of prime-numbers. We take circumferences equal to 700cm,1100cm 1700 cm to consider prime numbers like 7,11 and 17[assuming that they do not divide N]. Points corresponding to the multiples of 7,11 and 17 marked on the three wheels separately.
This time the the marked points on three wheels would eliminate multiples of 7,11 and 17 . Some ummarked integral point[which is not a multiple of the three primes mentioned] should correspond to the required divisor.By coupling these wheels to some gadget like the microprocessor we might save some time.

 

[Anamitra]

On "Transfers"[This is in relation to posts 4 and 5]
Lets us consider the following expressions[ of post 5]

$${x}^{3}{-}{15x}{-}{4}{=}{(}{x}{-}{4}{)}{(}{x}^{2}{+}{4x}{+}{1}{)})$$ ----- (1)
and
$${x}^{3}-{15x}{-}{126}{=}{0}$$------------- (2)
Soln for eqn(2): x=6

We now consider separately the second factor on the RHS of in expression (1)
$${x}^{2}{+}{4x}{+}{1}$$
$${=}{x}^{2}{+}{3x}{+}{x}{+}{1}$$
$${=}{x}^{2}{+}{3x}{+}{6}{+}{1}$$
[since x=6]
$${=}{x}^{2}{+}{3x}{+}{7}$$
I would like to point out to the fact that the transfer of x from 4x to the next term to its right making it x+1=7 can modify the functional expression for the entire factor without changing its value so long as we keep x=6.
So we may rewrite identity (1) as
$${(}{x}{-}{4}{)}{(}{x}^{2}{+}{3x}{+}{7}{}){=}{x}^{3}{-}{x}^{2}{-}{5x}{-}{28}$$ -----(3)
and equation (2) as
$${x}^{3}{-}{x}^{2}{-}{5x}{-}{28}=122$$ -----------(4)
The above equation again produces the soln x=6 and the modified identity produces the factors 2 and 61.
This method of transfers shows that for the same integral solution we may have several "initial identities". This is somewhat encouraging.

Now let us turn our attention to relations (1),(2) and (3) of posting 2.
For the same value of the base the expressions for N,A and B can have several functional forms,preserving the values of N,A and B.
For N we simply work out the transfers in such a way that the longer summation terms of the form $${\Sigma}{a}_{i}{b}_{j}{=}{c}_{p}$$ have larger integral values for $${c}_{p}{,}{where}{,}{p}{=}{i}{+}{j}$$.This may be done arbitrarily.Now,there is a huge number of alternatives--the functional expression for N may be transformed in a multitudinous number of ways preserving its own value and the value of the base. But the positively encouraging fact is the expressions for A and B can have several functional forms that preserve their individual values and the value of the base. This appears to favor the probability of success in locating a correct match of expressions for N=A*B[This time we use the method of equating the coefficients of identical powers of x on the two sides of N=A*B after substituting their functional forms, with the hope of obtaining integral values for ai and bk]

 

[Anamitra]

A Rough Estimation of the Probability of Success:

[Provided the highest powers in the factorized terms [m,n:m+n=p] ; p is the highest power of base[=x] in the initial expansion of N; N=A*B where A and B are large primes; m and n are the highest powers of base in A and B]

Let us first calculate the total number of transformed expressions produced by the method of transfers[the coefficients are constrained to maintain integral values].

Initial expansion[in the powers of base]:

$${f(x)}{=}{a}_{p}{x}^{p}{+}{a}_{p-1}{x}^{p-1}{+}{...}{a}_{1}{x}{+}{a}_{0}$$ ------------------------ (1)

The highest coefficient value for any power of base [for the initial expansion]=9
The highest power of base can provide 9 transfers[from 8 to zero] to the next lower power[it will not transfer everything to preserve the highest power].
p is the highest power of x in the expansion.
If x^p transfers 8*x^r to x^(p-1) this term receives as coefficient 80. So it can have a maximum coefficient value 89 . It can make 90 transfers to 10^(p-2).This includes the zero transfer case.
If 7*10^p is transferred x^(p-1) receives 80 as coeff and the maximum coeff it can have now is 79. It is capable of 80 transfers to x^(p-2)
If 1*10^p is transferred x^(p-1) receives 10 in the coefficient. THe maximum value of the coefficient is 19 . It can make 20 transfers to 10^(p-2)
If no transfer is made the digit in x^(p-1) has a maximum value of 9. It is capable of 10 transfers to the next lower power.
The total number of ways transfers can be made to from 10^(p-1) to 10^(p-2)
= 90+..... +20+10Let the largest possible coeff of 10^r be k(r). k(r) may be larger than 9 since it might have received transfers from previous higher higher powers.
The maximum increment of coefficient of 10^(r-1) after the highest transfer from 10^r is 10k(r). The maximum digit/coefficient it[10^(r-1)] can have now is k(r-1)=10k(r)+9. ----- (2)
The number of possible transfers to x^(r-2) is :
T(r-2)=[10k(r)+10)]+[10{(k(r)-1}+10]+[10{k(r)-2}+10]+...+[10+10]+10 -----(3)
Zero-transfer cases from the coeff of x^(r-1)have been included.

[For the position 10^(r-2) transfers from the coefficients of positions higher than 10^(r-1),without involving any transfer from the coeff of 10^(r-1) has been taken care of in an indirect manner.]

T(r-2)=5[k(r)]^2+15k(r) +10
T(r-3)=5[k(r-1)]^2+15k(r-1) +10
Where,
K(r-1)=10k(r)+9
K(r)=10^(p+1)/[10^r] - 1
T(r-2)=5[10^(p+1)/[10^r] - 1 ]^2 + 15[10^(p+1)/[10^r] - 1 ]+10
T(r-1)=5[10^(p+1)/[10^(r-1)] - 1 ]^2 +15 [10^(p+1)/[10^(r-1)] - 1 ]+10
We have to calculate T(0) which is the total number of transfers
Putting r=1
T(0)=5[10^(p+1)-1]^2+15[10^(p+1)-1]+10

Regarding Equation (2)

For accuracy we may modify it to write
k(r-1)=10k(r)+a(r-1) ---- (4)

a(r-1) is the coeff of x^(r-1) in the initial expansion

Equation (3) changes to:
T(r-2)=[10k(r)+a(r-1)+1]+[10{(k(r)-1}+a(r-1)+1]+[10{k(r)-2}+a(r-1)}+1]+...+[10+a(r-1)+1]+a(r-1) ---------- (5)
T(r-2)=5k(r)[k{r}+1]+k*a(r-1) --------------- (6)Points To Note:
1.Transfers from higher to lower powers of "x"[=10] have been considered . The coefficients are always positive and integral
2.The value of the number represented by the expansion does not change.
3. The values of m and n assumed to be known

[THIS POST WILL BE REVISED]

 

[Anamitra]

REVISED METHOD
Let us consider the expression:
$${f}{(}{x}{,}{n}{)}{=}{a}_{n}{x}^{n){+}{a}_{n-1}{x}^{n-1}{+}{a}_{n-2}{+}$$
$${a}_{n-2}{x}^{n-2}{+}{……..}{a}_{1}{x}{+}{a}_{0}$$ ----------------- (1)
[X=10 and the above expression has n+1 terms]
Let the total number of possible transformations of (1)[ie the number of transformed equations] by the transfer process [with the given configuration of coefficients] be denoted by $${T}{(}{n}{:}{ configuration}{)}$$, where “n” is the highest power of the base. Now we extend the power to x^(n+1) with coeff
$${=}{a}_{n+1}$$
Our modified expression:
$${f}_{m}{(}{x}{,}{n+1}{)}{=}{a}_{n+1}{x}^{n+1}{+}{a}_{n}{x}^{n){+}{a}_{n-1}$$
$${x}^{n-1}{+}{a}_{n-2}{+}{a}_{n-2}{x}^{n-2}$$
$${+}{……..}{a}_{1}{x}{+}{a}_{0}$$ ----------------- (2)
The above expression has n+2 terms
We may distribute/partition the $${a}_{n+1}$$ among the other terms[including the newly added one] in $${{}{a}_{n+1}{+}{n}{+}{1}}{)}{C}{(}{n}{+}{1}{)}$$ ways.
Total no of configurations
$${=} {(}{a}_{n+1}{+}{n}{+}{1}}{)}{C}{(}{n}{+}{1}{)}{T}{(}{n}{:}{configuration}{})$$
In these configurations we have considered the destruction of the highest power itself[ie, x^(n-1).We will not do this with the last extension
Let the last ,ie, the highest power in our extension M=n+k
$$T{(}{M}{)}{=}{T}{(}{n}{+}{k}{)}$$
$${=}{(}{a}_{n+k}{+}{n}{+}{k}{-}{1}{)}{C}{(}{n}{+}{k}{)}{\Pi}{(}{{}{a}_{n+i}{+}{n}{+}{i}}{)}{C}{(}{n}{+}{i}{)}{T}{(}{n}{:}{configuration}{)}$$------ (3)
I runs from 1 to k-1
Let us consider the synthesis of expression: $${a}_{1}{x}{+}{a}_{0}$$ from the constant term a0.
The possible number of configurations=$${[}{a}_{1}{+}{1}{]}{C}{1}$$$${=}{a}_{1}{+}{1}$$----(4)
We may rewrite relation (3) as:
$$T{(}{M}{)}{=}{(}{a}_{M}{+}{M}{-}{1}{)}{C}{(}{M}{)}{\Pi}{(}{{}{a}_{i}{+}{i}}{)}{C}{i}$$------ (5)
If N=A*B, A and B are primes we may apply formula (5) to each of the expressions for N ,A and B to get the probability of success provided we know the highest powers of A and B[m and n respectively:m+n=p
Let us calculate the probability of success for N having highest power of base[=10] as 400
Let the correct value of m be 196 and hence that of n,204
Probability of success:
In the numerator we have the following terms in product form:
1. $${(}{203}{+}{a}_{m}{-}{1}{)}{!}{(}{203}{+}{a}_{m-1}{)}{!} {(}{202}{+}{a}_{m-2}{)}{!}{…………..}{(}{a}_{1}{+}{1}{)}$$
2. $${(}{195}{+}{b}_{n}{-}{1}{)}{!}{(}{195}{+}{b}_{n-1}{)}{!}{(}{194}{+}{b}_{n-2}{)}{!}{……..}{(}{b}_{1}{+}{1}{)}$$
3. $${400}{!}{399}{!}{………}{2}{!}$$

In the denominator
1. $${(}{399}{+}{c}_{p}{-}{1}{)}{!}{(}{399}{+}{c}_{p-1}{)}{!} {(}{398}{+}{c}_{p-2}{)}{!}{…………..}{(}{c}_{1}{+}{1}{)}$$
2. $${204}{!}{203}{!}{………}{2}{!}$$
3.$${196}{!}{195}{!}{…….}{2}{!}$$
There is a big scope for favorable cancellations . It appears that the probability would be much greater than 1/[10^200]

REVISION WILL BE WORKED OUT
REASON: With every new addition of a higher power: $${a}_{n+1}{x}^{n+1}$$, T(n) will change.
If 5*10^5 is added to the expression where the highest power was previously 10^4,
the smallest contribution to 10^2 term[from the new term] will be 10^3*10^2. This may again be redistributed to the lower orders in packets of 10^2 which was not possible directly from the 10^5 term
This might improve the probability of success. But I am not confirming at this point of time.

 

[Anamitra]

Could this Simplify the Problem?

We choose a number system with a very large base, say 10^120.
The number system will have a huge number of digits. But the larger numbers will have a fewer number of digits.
If a 400 digit number now has four digits, we have cubic polynomial:

$${A}{x}^{3}{+}{B}{x}^{2}{+}{C}{x}{+}{D}{=}{N}$$
[x is a large base]

It will factorize in the form:

$${(}{a}{x}{+}{b}{)}{(}{p}{x}^{2}{+}{q}{x}{+}{r}{)}$$
Though A,B,C,a,etc are large numbers[very much unwieldy],the transfer problem should become simpler in nature[for the calculation of the probability of success].

 

[Anamitra]

An Interesting Strategy
It would be interesting to look for the two factors[the two primes ] in decimal form[base=10]
The coefficients in the product term will be of the form:

$${\Sigma}{a}_{i}{b}_{k}$$ ------------ (1)

[ai and bk are coefficients from the decimal expansions of the two primes]

Each product is of the form $${a}_{i}{b}_{k}{\le}{81}$$
Since we are working in the decimal system each ai and bk is individually less than 9
So each product term can take on discrete values from zero to 81
The highest value a summation with n product terms is n*81.[n is the number of product terms in the summation represented by (1)]
This can be an interesting constraint in favor of our work at hand.The transfer process[and this process is operated on the composite number expressed in the decimal system] is expected to get simplified. We don't have to bother ourselves with a huge number of unnecessary transfers.
[Remembering this constraint we should try to assign higher values to the coefficients in the composite number corresponding to the longer summations,while working out the transfer process]

To find the correct location of the highest powers of the base[=10] in the factors[that is, the primes] we have to run several simultaneous programs. For a 400 digit number we may have to run 200 [or a few more ] programs.The one with the correct values of the highest powers should do well.

Important Point to note:
If the coefficient in the term with base power 50, is 4 and we transfer 2 units of coefficient from this term to the one with base power 45, the coefficient of this base power increases by 2*10^5=200,000.[base=10]
If the longest summation has 200 product terms the maximum value of coefficient it[ie,the expression] can entertain is 200*81=16,200 [if the individual primes are to be evaluated in the decimal system.]
[The highest power of base [=10] may be assumed to be 400]

 

[Anamitra]

Referring to my previous post,we have
$${a}_{i}{b}_{k}{\le}{81}$$

If the digits appear randomly, the expected value of a digit
$${[}{1}{/}{10}{]}{(}{0}{+}{1}{+}{2}{+}{3}{...}{9}{)}{=}{4.5}$$

One may take the approximate value of a digit=5
Therefore,

$${\Sigma}{a}_{i}{b}_{k}{\approx}{25n}$$

[Here "n" is the number of product terms in the above summation]

This "probability assumption" is supposed to work conveniently with the product of larger prime numbers having a huge number of digits.[The longer summations should be more responsive to this type of treatment]

We might think of an initial trial expression for composite number using the above technique before moving towards[iterating towards] the correct one.

This perhaps could be a step towards simplification
[NB: The initial trial expression may not represent the exact value of the composite number.Nevertheless it will help us in predicting the correct coefficient pattern/distribution of this number for decimal factorization.

 

[Anamitra]

A Useful Property
N=A*B

Let 2k=A+B
2n=A-B
A=(K+n)
B=(k-n)
$${N}{=}{k}^{2}{-}{n}^{2}$$ -------------- (1)
Or
$${N}{+}{n}^{2}{=}{k}^{2}$$ ------------ (2)

We must have unique values for n and k since the two prime factors are n+k and n-k [from (1)] This takes care of the prime-ness property of A and B
Let $${N}{=}{\Sigma}{a}_{i}{x}^{i}$$
$${n}{=}{\Sigma}{b}_{j}{x}^{j}$$
$${k}{=}{\Sigma}{c}_{k}{x}^{k}$$
Equation (2) may be written as:
$${\Sigma}{a}_{i}{x}^{i}{+}{{[}{\Sigma}{b}_{j}{x}^{j}{]}}^{2}{=}{{[}{\Sigma}{c}_{k}{x}^{k}}{]}^{2}$$i runs from 0 to n for N; j and k should run from zero to sqrt[n] rounded to the nearest integer[A=n+k< N]. We might obtain zero-value coefficients to achieve this effect in the method to follow:

Equating coefficients corresponding to equal powers of x on either side we may solve the resulting equations[n in number].It is important to note that these equations are not independent.

If, somehow we can get an integral solution set it is the only one --the one corresponding to our requirement

[The identity represented by (1) or (2) was used by Fermat in the 17th century. This interesting information was provided to me by Dr Jacques of Math Forum[Ask Dr Math] when I submitted the contents of this post[only the first part of it] at Ask Dr Math]

 

[Anamitra]

The Closeness/Remoteness Trial Method

N=A*B, where A and B are primes

$${N}^{'}{=}{[}{a}_{m}{x}^{m}{+}{a}_{m-1}{x}^{m-1}{+}{...}{a}_{1}{x}{+}{a}_{0}{]}{[}{b}_{n}{x}^{n}{+}{b}_{n-1}{x}^{n-1}{+}{...}{b}_{1}{x}{+}{b}_{0}{]}$$

We approximate N by a product of the type shown in the relation above.We assign arbitrary values to the coefficients ai and bk . We may start with values lying between 0 and 9. The highest powers m and n in the two product terms may be assigned high values arbitrarily.For example if N is a 400 digit number we may take m=n=250 at the initial stage.[One may start with a known composite number close to N which may have factors of comparable magnitude---the difference in the number of digits is not very large]

We calculate the value of N' and observe its closeness or remoteness wrt N. Then we start adjusting the coefficients to make N' closer to N. The coefficients are always maintained integral. But now we may take any integral value --positive values greater than 9 or even negative values.One may also use fractional values for the coefficients for which the denominators contain powers of 2 and 5 in product form---an integral value has to be obtained after multiplication with x^p=10^p. The value of x[=10] is kept unchanged.
The process is repeated to make Mod[N-N'] smaller and smaller.
This method has to be worked out on a computer.

 

[Anamitra]

N=A*B, where A and b are primes-------------------- (1)
$${A}{=}{a}_{m}{x}^{m}{+}{a}_{m-1}{x}^{m-1}{+}{……….}{a}_{1}{x}{+}{a}_{0}$$ ------------- (2)
$${B}{=}{b}_{n}{x}^{n}{+}{b}_{n-1}{x}^{n-1}{+}{……….}{b}_{1}{x}{+}{b}_{0}$$ ----------- (3)
Now if we use the substitutions
$${a}_{i}{--- >}{{a}_{i}}{n}$$
$${b}_{i}{--- >}{{b}_{i}}{/}{n}$$
Equation (1) will continue to hold. But A and B will not be primes.
Looking from the reverse direction, by solving equation (1) by equating coefficients on either side of it we might, in all probability obtain non-integral solutions for A and B. But by multiplying one solution by a suitable n and by dividing the other by n we may try to obtain the primes. Several values of n may be tried out on a computer/microprocessor.

We may divide a large N[=AB] by a number say 2.5 and get a quotient I.pqest….j
I represents the integral part. The rest is the fractional part.[ A terminating decimal part will make things simpler:It would be convenient to look for a rational no. of the form I.pqrst...j ]
Now one should look for a fraction[rational] such that:
I.pqrst….j * Fraction = Integer[say,S] ------------- (2)
And then try out{ 2.5/Fraction} [ =K]. If the result is an in integer our work is done.

Point to Take Note of:
If 2.5/Fraction ie, K contains a fractional part then we have the following:
N= KS
N=[a/b]*S where, [K=a/b: this will give an advantage only if K is rational]]
b*N=a*S
If b is prime wrt to a [that is,they have no common prime factors],if N does not divide a or b, and if b is less than S it should divide S ,factorizing N

[Instead of taking 2.5 one may take some figure close to Sqrt[N] ]

 

[Anamitra]

N=A*B, where A and B are primes.

Let us express N in the following way

$${N}{=}{A}_{1}{+}{A}_{2}{+}{A}_{3}{+}{...}{A}_{10}$$

We break up each A1 into prime factors
The RHS is factorizable and only two factors are possible.
A possible case:

$${A}_{1}{+}{A}_{2}{+}{A}_{3}{=}{K}$$
and this K is a prime contained in each of the the other summation terms.

One could use a larger number of terms in the summation. A smaller number of terms could prove useful if we happen to know all the prime factors in each of them.