Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Should We Take the Long Strides?
Posted:
Jan 10, 2012 8:00 AM


We consider a semiprime 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(x1)+Q+R The new remainder is Q+R, provided Q+R<x1
Quotient remaining the same[ie,Q] we have the following relation for n divisions by successive divisors decreasing in steps of unity: N=Q(xn)+nQ+R If xn>nQ+R then nQ +R is indeed the remainder after n steps: n<{xR}/{Q+1} The largest value of n before the quotient increases is the least integer greater than or equal to than {xR}/{Q+1}. If n={xR}/{Q+1} the higher factor,B, has been located [since remainder becomes zero]. For the next division[Divisor:xn1] the quotient should increase.
Stage B Now N=Qx+R If the remainder increases by unity: N=(Q+1)(x1)+R+Qx+1 New remainder: R¹=R+Qx+1 For n¹ steps[Quotient remaining Q+1] we have: R¹=R+n¹Qx+n For R¹>=0 we have, Rx>=n¹(Q+1) =>n¹=<{Rx}/{Q+1}
The last remainder from Stage A: =nQ+R The last divisor from Stage A:xn Using the final approximate value of n[=(xR)/(Q+1)] and x[=(xn)] from the previous stage we have: n¹={nQ+R(xn)}/{Q+1} [approx.] n¹={n(Q+1)+Rx}/{Q+1} [approx] n¹ approximately equal to n{xR}/{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 smallestvalue 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#RSA280]. 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^2798 * 10^278]=0.5[10 * 10^2788 * 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?



