No subject

["Jürgen Bullinger"]

Hello all,

thank you for all your answers!

I just thought, that operations like 2^n (mod m) could be performed faster,
because the necessary multiplication is just a bit shift.
But I must admit, that I don't know how the FFT multiplication works.

If it was faster than for other operands maybe it would be a great way to do
a first check in a primality test, because I guess it would be possible to
sort out a great deal of composite numbers before a more costly algorithm is
applied. Whether it is better to use this step or not might be depending on
how probable the tested numbers are considered to be prime.

To the other comments about the primality test I am doing:
I know that a check like in the one according the little theorem by fermat
generally isn't save because a^(p-1) mod p=1 doesn't neccessarily meen that
the number is prime, but for the numbers I am observing the fermat check is
almost sufficient.

The following is a little technical and not really neccessary for the
thread, but maybe some of you would like to know why fermat's little theorem
is enough for this kind of numbers:

I use ord(x) as the multiplicative order to a natural number "a" greater
than 1. Normally this is written as "ord_x a", but is hard to read here. I
hope this is not confusing.

I observe numbers m like

m=p*n+1 

where p is prime and 2 <= n <= p

for this special numbers i do a check according to fermat's little theorem.
If the number m passes the test it means that phi(m) divides p*n.

This means that for all the prime factors p_i in m the following is true:

ord(p_i) divides p*n (consequence of the fermat-euler-theorem which is an
extension to fermat's little theorem).
If m is composite it means that there must be at least on factor p_i <=
sqrt(m). Because of the form of sqrt(m)<p.
Now we have ord(p_i) divides p*n and p_i<p. This leads to ord(p_i) divides n
because p is prime.
So if m is composite and passes the check according the FLT it means, that
at least one of it's factors must also be a factor of a^n-1.
So it is really only necessary to check if the FLT-check is positive and
then ceck if gcd(p*n+1,a^n-1)=1 to proove that p*n+1 is prime.

So in fact I don't need a more secure primality check. I just wodered if
there might be a faster check to sort out some composite numbers just before
I apply the FLT-check. I already do some sieving based on trial divisions.

Kind regards

Jürgen

-- 
10 GB Mailbox, 100 FreeSMS/Monat http://www.gmx.net/de/go/topmail
+++ GMX - die erste Adresse für Mail, Message, More +++