# No subject

"Jürgen Bullinger" juergen.bullinger at gmx.net
Tue Nov 15 17:36:38 CET 2005

```Hello all,

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.

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 +++
```