Hi:
I've been thinking a while about posted articles about the challenge
George Woltman give to us.
IMHO, the algorithms G. Woltman has written to find factors up to 64 bits
has two important advantages (in addition to his ability and intelligence
in programming), the use of FPU to multiply and the precomputed 1/f (f is
the trial factor).
Now, for factors bigger than 2^64-1 we have a lot of practical problems to
use similar algorithms. I am wondering if there is a good thing to continue
with the use of FPU.
I have an idea (I don't know if new and useful) to do a previous work before
go to the inner most loop. I'll try to show it. Sorry by my awful English.
Our task is to calculate 2^p mod f, if the result is 1, then we've hunted a
factor. This task drives us to the task to compute (a*a) mod f as fast as
possible.
In next lines, f is the trial factor and a is a positive integer less than f.
a) We will suppose we have the fastest algorithm to compute a*a . (if f has
less than n significant bits, a*a has less than 2*n bits ). We also suppose
there is a fast function bit(a*a,j) which gives the j'th bit of a*a (0<=j<=2*n).
b) Once computed a*a, the hard task is to do (a*a) mod f, but note that this
task we have to do many times (the number of bits for p minus 6) for different
a's in modular exponentiation. My Thought is try to find mod f faster.
To do this we will first to construct a table of 2^m mod f, for m from n+1 to
m=2*n. This is very easy to do (this c-code has to be implemented in assembler):
{ j=n+1;// starting exponent
r=2^(n+1);// the first power greater than f
do
{ if (r<f)
{ t[j]=r; r=r+r; j=j+1;} // t is the array
else
{ r=r-f;};
} while (j<=2*n)
}
After that, t[j] = 2^(j) mod f
Then, in every iteration, we compute b=a*a
This c-code evaluates r= b mod f
{
r= (b & 2^n-1); // r is the n less significant bits of b.
if (r>f) r=r-f;
j=n+1;// Starting bit
d
o
{
if (bit(a2,j)) {r=r+t[j]; if (r>f) r=r-f;}
j=j+1;
} while (j<=n+1)
}
It will have an average of n/2 multi-words additions and subtractions to
compute b mod f (assuming there is half ones in binary expression of b).
There is an alternative way to compute a*a mod f without a previous
multi-word multiplication to compute a*a. (I think this is the method
B.J.Beesley has written, the first one), I'm not sure, but I think it costs
3*n/2 multi-words additions and subtractions in average. In c-code, it
would be something like:
{
r=0 ;
x=a ;// first auxiliary remainder
j=0 ;// first bit to check in a
do {
if(x>=f) x=x-f; // x now is a^(2^j) mod f
if (bit(a,j)) // look at j'th bit of a
{
r=r+x;
if(r>=f) r=r-f;
};
x=x+x;
j=j+1;
} while (j<=n)
}
The question is �How fast we can compute a*a? If we can do it faster than
n additions and subtractions (n can vary from 64 to 80), we perhaps can save
some CPU time.
What do you think?. This is only an unfinished idea.
Yours sincerely.
*********************************
Guillermo Ballester Valor
[EMAIL PROTECTED]
c/ C�rdoba 19
18151-Ogijares Spain
*********************************
