Should We Take the Long Strides?

[Anamitra Palit]

We consider a semi-prime N=AB, where  A and B are primes.
We assume B>A
Stage A:

Letıs consider the relation:
N=Qx+R
X:Divisor
Q: Quotient and
R:Remainder
We write:
N=Q(x-1)+Q+R
The new remainder is Q+R, provided Q+R<x-1

Quotient remaining the same[ie,Q] we have the following relation for n
divisions by  successive divisors decreasing in steps of unity:
N=Q(x-n)+nQ+R
If x-n>nQ+R
then nQ +R is indeed the remainder after n steps:
n<{x-R}/{Q+1}
The largest value of n before the quotient increases is the least
integer greater than or equal to than {x-R}/{Q+1}. If  n={x-R}/{Q+1}
the higher factor,B, has been located [since remainder becomes zero].
For the next division[Divisor:x-n-1] the quotient should increase.

Stage B
Now
N=Qx+R
If the remainder increases by unity:
N=(Q+1)(x-1)+R+Q-x+1
New remainder:
Rı=R+Q-x+1
For nı steps[Quotient remaining Q+1] we have:
Rı=R+nıQ-x+n
For
Rı>=0 we have,
R-x>=nı(Q+1)
=>nı=<{R-x}/{Q+1}

The last remainder from Stage A:
=nQ+R
The last divisor from Stage A:x-n
Using the final  approximate value of n[=(x-R)/(Q+1)] and x[=(x-n)]
from the previous stage we have:
nı={nQ+R-(x-n)}/{Q+1}  [approx.]
nı={n(Q+1)+R-x}/{Q+1}  [approx]
nı approximately equal to n-{x-R}/{Q+1}
This implies: nı<n, rather nı<<n for large values of the divisor x

If the division result for the first operation in stage A is known to
us ,we immediately come to know of all the division results of stage A
and B[and of subsequent stages] from formulas without doing actual
division. The result of each individual operation is not necessary. We
simply have to calculate the values of n and nı and check out for the
smallest-value remainder in case it is zero. The zero remainder might
occur at the end of Stage A or Stage B while we are investigating the
upper integral from N to Sqrt[N],decreasing the divisor in steps of
unity.

Why the ³Strides² are long:
Letıs take N=RSA 280 by way of example [Link:
http://en.wikipedia.org/wiki/RSA_numbers#RSA-280].
It has 280 decimal digits. We choose the first divisor as 10^279.
Remainder, R is less than 8 * 10^278. Quotient, Q=1 . Therefore n is
greater than 0.5[10^279-8 * 10^278]=0.5[10 * 10^278-8 *
10^278]=10^278. The next divisor to be taken up is 10^279 -  10^278=9
* 10^278. So we are taking long strides for large divisors. In this
example the number of digits in the divisor is being reduced by one.
Subsequent strides would become  smaller.
How many strides[Stride=A+B] do we need to cover the higher interval
from N to sqrt[N]
Would this method be convenient on the microprocessor?