Campo modulare#12317

Campo modulare (Editoriale)

Il numero $c$ \sqrt{c} è irrazionale, quindi calcolare l'espressione in numeri reali non ha senso: per $n$ fino a $1 0^{18}$ 10^{18} ciò è impossibile per questioni di precisione. Notiamo, tuttavia, che qualsiasi potenza intera del numero $a + b c$ a + b\sqrt{c} ha ancora la forma $x + y c$ x + y\sqrt{c}, poiché $c \cdot c = c$ \sqrt{c} \cdot \sqrt{c} = c. Pertanto, i calcoli vanno eseguiti nel campo esteso:

Z_{p} (c) = {x + y c ∣ x, y \in Z_{p}}

Z_p (\sqrt{c}) = \{ x + y \sqrt{c}~|~x,y \in Z_p\}

Regole delle operazioni:

Addizione

(x_{1} + y_{1} c) + (x_{2} + y_{2} c) = (x_{1} + x_{2}) + (y_{1} + y_{2}) c

(x_1 + y_1 \sqrt{c}) + (x_2 + y_2 \sqrt{c}) = (x_1 + x_2 ) + (y_1 + y_2) \sqrt{c}

Moltiplicazione

(x_{1} + y_{1} c) \cdot (x_{2} + y_{2} c) = (x_{1} x_{2} + c y_{1} y_{2}) + (x_{1} y_{2} + x_{2} y_{1}) c

(x_1 + y_1 \sqrt{c}) \cdot (x_2 + y_2 \sqrt{c}) = (x_1 x_2 + cy_1 y_2) + (x_1 y_2 + x_2 y_1 ) \sqrt{c}

Dopo aver definito l'operazione di moltiplicazione, gli elementi del campo $Z_{p} (c)$ Z_p (\sqrt{c}) possono essere elevati a potenza con il metodo standard dell'elevamento a potenza veloce in tempo $O (l o g_{2} n)$ O(log_2n). Questo permette di calcolare $(a + b c)^{n} m o d p$ (a + b \sqrt{c})^n~mod~p.

Esempio

Nel primo esempio

(2 + 5)^{2} m o d 17 = (4 + 45 + 5) m o d 17 = 9 + 45

(2 + \sqrt{5})^2~mod~17 = (4 + 4 \sqrt{5} + 5)~mod~17 = 9 + 4 \sqrt{5}

Consideriamo il secondo esempio:

(3 + 25)^{10} m o d 17

(3 + 2 \sqrt{5})^{10}~mod~17

Sia $x = 3 + 25$ x = 3 + 2 \sqrt{5}. Calcoliamo le sue potenze:

x^{2} = (3 + 25)^{2} m o d 17 = (9 + 125 + 20) m o d 17 = 12 + 125 x^{4} = (12 + 125)^{2} m o d 17 = (144 + 2885 + 720) m o d 17 = 14 + 165 x^{8} = (14 + 165)^{2} m o d 17 = (196 + 4485 + 1280) m o d 17 = 14 + 65

x^2 = (3 + 2 \sqrt{5})^2~mod~17 = (9 + 12 \sqrt{5} + 20)~mod~17 = 12 + 12 \sqrt{5} \\ x^4 = (12 + 12 \sqrt{5})^2~mod~17 = (144 + 288 \sqrt{5} + 720)~mod~17 = 14 + 16 \sqrt{5} \\ x^8 = (14 + 16 \sqrt{5})^2~mod~17 = (196 + 448 \sqrt{5} + 1280)~mod~17 = 14 + 6 \sqrt{5}

Ora possiamo calcolare il risultato:

x^{10} = x^{8} \cdot x^{2} = (14 + 65) (12 + 125) m o d 17 = (168 + 725 + 1685 + 360) m o d 17 = 1 + 25

x^{10} = x^8 \cdot x^2 = (14 + 6 \sqrt{5})(12 + 12 \sqrt{5})~mod~17 = \\ (168 + 72 \sqrt{5} + 168 \sqrt{5} + 360)~mod~17 = 1 + 2 \sqrt{5}

Implementazione dell'algoritmo

Dichiariamo la struttura $N u m$ per memorizzare un numero della forma $x + y c$ x + y \sqrt{c}.

struct Num
{
  long long x, y; // x + y*sqrt(c)
};

Implementiamo la moltiplicazione nel campo $Z_{p} (c)$ Z_p (\sqrt{c}). La funzione mult restituisce il prodotto dei numeri $a$ e $b$ .

Num mult(Num
{
  Num res;
  res.x = (a.x * b.x + c * a.y % p * b.y) % p;
  res.y = (a.x * b.y + a.y * b.x) % p;
  return res;
}

C++

La funzione pow implementa l'elevamento a potenza $ba s e^{n}$ base^n, dove $ba se$ — è un numero nel campo $Z_{p} (c)$ Z_p (\sqrt{c}).

Num pow(Num base, long long n)
{
  Num res = { 1, 0 }; // unità del campo
  while (n > 0)
  {
    if (n & 1)
      res = mult(res, base);
    base = mult(base, base);
    n >>= 1;
  }
  return res;
}

C++

Parte principale del programma. Leggiamo i dati in ingresso.

scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &n, &p);

Inizializziamo il numero iniziale $s t a r t = a + b c$ start = a + b \sqrt{c}.

Num start = { a % p, b % p };

Calcoliamo e stampiamo la risposta $an s = s t a r t^{n} m o d p = (a + b c)^{n} m o d p$ ans = start^n~mod~p = (a + b \sqrt{c})^n~mod~p.

Num ans = pow(start, n);
printf("%lld %lld\n", ans.x, ans.y);