# mpz_powm function for complex and adjoined numbers

Bernhard Helmes bhelmes at gmx.de
Sat Apr 24 13:09:46 CEST 2010

```A beautifull day,

> > is there a powermod function for complex numbers and adjoined numbers ?

Is it possible to speed up these two functions

1. This calculates (re + im*I)^exp mod f
result is in real, imag

mpz_t Are, Bim, AAre, BBim, re, im, erg, erg3, f
mpz_init (Are);
mpz_init (Bim);
mpz_init (AAre);
mpz_init (BBim);
mpz_init (re);
mpz_init (im);
mpz_init (real);
mpz_init (imag);
mpz_init (erg);
mpz_init (erg3);
mpz_init (f)

int powermod_I (mpz_t re, mpz_t im, unsigned long int exp, mpz_t f)
{
unsigned long int bit;

bit=exp % 2;

mpz_set (AAre, re);
mpz_set (BBim, im);

if (bit==1)
{
mpz_set (Are, re);
mpz_set (Bim, im);
}
else
{
mpz_set_ui (Are, 1);
mpz_set_ui (Bim, 0);
}

exp=(exp-bit)/2;

while (1)
{
bit= exp % 2;
exp=(exp-bit)/2;

mpz_mul (erg, AAre, AAre);
mpz_mul (erg3, BBim, BBim);
mpz_sub (erg, erg, erg3);
mpz_mod (erg, erg, f);

mpz_mul (erg3, AAre, BBim);
mpz_mul_ui (erg3, erg3, 2);
mpz_set (AAre, erg);
mpz_mod (BBim, erg3, f);

if (bit==1)
{
mpz_mul (erg, Are, AAre);
mpz_mul (erg3, Bim, BBim);
mpz_sub (erg, erg, erg3);
mpz_mod (erg, erg, f);

mpz_mul (res, Are, BBim);
mpz_mul (erg3, Bim, AAre);
mpz_mod (Bim, Bim, f);

mpz_set (Are, erg);
}

if (exp==0)
{
mpz_set (real, Are);
mpz_set (imag, Bim);
return (0);
}
}
}

2. This calculates (r_s + i_s*sqrt (adj))^exp mod p
result is in r and i,
exponent should be odd;

mpz_t r, i, rr, ii, rrr, iii, res;
mpz_init (r);
mpz_init (i)
mpz_init (rr);
mpz_init (ii)
mpz_init (rrr);
mpz_init (iii);
mpz_init (res);

int powmod_adjoin (unsigned long int r_s, unsigned long int i_s, unsigned long int exp, unsigned long int p, unsigned long int adj)
{
unsigned long int bit;

bit=exp % 2;
mpz_set_ui (a, r_s);
mpz_set_ui (b, i_s);
mpz_set_ui (rr, r_s);
mpz_set_ui (ii, i_s);
mpz_set_ui (r, r_s);
mpz_set_ui (i, i_s);
exp=(exp-1)/2;

while (1)
{
bit= exp % 2;
mpz_mul (rrr, rr, rr);
mpz_mul (res, ii, ii);
mpz_mod_ui (rrr, rrr, p);
mpz_mul (iii, ii, rr);
mpz_mul_ui (iii, iii, 2);
mpz_mod_ui (iii, iii, p);
mpz_set (rr, rrr);
mpz_set (ii, iii);
if (bit==1)
{
mpz_mul (rrr, r, rr);
mpz_mul (res, i, ii);
mpz_mod_ui (rrr, rrr, p);
mpz_mul (iii, r, ii);
mpz_mul (res, i, rr);
mpz_mod_ui (iii, iii, p);
mpz_set (r, rrr);
mpz_set (i, iii);
}

exp=(exp-bit)/2;
if (exp==0)
{
return (0);
}
}
}

Nice Greetings from the primes
Bernhard

http://www.devalco.de
--
www.devalco.de         Development of Algorithmic Constructions
www.rabbitweb.de      Jugglevideos
www.beablue.de         personal web page

Tel.: 0241 / 99 77 55 22 in Germany (0049)

--
www.devalco.de         Development of Algorithmic Constructions
www.rabbitweb.de      Jugglevideos
www.beablue.de         personal web page

Tel.: 0241 / 99 77 55 22 in Germany (0049)

```