Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Should We Take the Long Strides?
Posted:
Jan 10, 2012 8:00 AM
|
|
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?
|
|
|
|
