Re: modular exponentiation

["Karim Belabas" <belabas@math.u-bordeaux1.fr>]

[private mail cross-posted to pari-users since it might be of general interest]

* Joerg Arndt [2005-12-14 14:31]:
> * Karim Belabas <belabas@math.u-bordeaux1.fr> [Dec 14. 2005 13:28]:
>> The exact strategy is as follows. If the modulus is word-sized (say < 2^32),
>> the powering is done directly with 'unsigned longs' (using Fl_pow() ),
>> not with all the (expensive) overhead of multiprecision.
> 
> Should just be shifts and bit-lookups(?)
> Why is it so expensive?

Not exactly expensive but, e.g, for a single multiplication of 2 integers,
represented as t_INTs, we must

  extract sign from 2 codewords (load + bit-and) [ no unsigned t_INT in PARI ]
  compare signs with each other and with 0 (test + test)
  extract length from 2 codewords (load + bit-and)
  compare the lengths with each other (test)
  compare length with thresholds for fast multiplication (test)
  extract mantissa (load + loop overhead, even though we look at 1 single word)
  multiply proper
  allocate result as a t_INT (test for available memory, shifts and
                              bitmasks to build codewords, save)

Compared to a single word multiply (using a suitable mul asm instruction),
this wastes between a factor 4 and 10. So as soon as we detect that a
not-so-trivial computation will definitely use only single word operands
we do that all the way through using dedicated routines.

To handle multiword exponents is not so dire, but you still waste a
number of shifts and loads and loop overhead for nothing. 
Since the fast routines alluded to above don't want to waste time for
useless tests, they are not implemented for this case (because there's
really no use for it). So you pay the price of not being able to use
fast routines besides the unnecessarily large exponent.

Cheers,

    Karim.
-- 
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]