Different bases = different times?

[roger]

I'm wondering how the amount of time to do primality tests changes with the base that is used with k.b^n+-1. I know that an odd base is not as quick as a base that is a power of two, but don't know if an even base has different times to complete primality tests than a power of two base.

Eg: k*2^n+1 = 10000 digits. k*62^n+1 = 10000 digits. Does the test time change?

Thanks,

Roger

[R.D. Silverman]

Originally Posted by roger

I'm wondering how the amount of time to do primality tests changes with the base that is used with k.b^n+-1. I know that an odd base is not as quick as a base that is a power of two, but don't know if an even base has different times to complete primality tests than a power of two base.

Eg: k*2^n+1 = 10000 digits. k*62^n+1 = 10000 digits. Does the test time change?

Yes.

The number of modular squarings is the same. Since k*b^n + 1, b!= 2
will have higher Hamming weight, the latter will have more multiplications
by b. [but note that multiplication by a single precision number does not
take much time.]

The biggest gain comes from the fact that it is MUCH faster to do modular
multiplication modulo k*2^n + 1 than for k*b^n + 1, b != 2.