Matematica: Un algoritmo per la risoluzione della congruenza Z^2=Q modp

Q

congruenza, previa verifica della loro esistenza, sono dati dal resto della divisione di per p , vale a

+

k 1

Q

z z z z

dire ≡ (mod p) e = p – . Il calcolo di può essere pertanto effettuato con un efficiente

1 2 1 1

algoritmo di esponenziazione modulare.. Diversi siti su Internet trattano questo algoritmo, ad esempio [SI0].

Per una sua esauriente esposizione e comprensione si rimanda all’esemplare articolo di C. Pomerance [Pom].

le seguenti [Cip]:

Nel caso poi in cui il primo p è della forma 8k + 5 le soluzioni della congruenza sono

+ − − −

p 3 p p p

1 1 1

1 2 2

Q Q

z z z

8 4 4 4

≡ · ( + 1 - ( - 1 ) · ) ( mod p ); = p –

1 2 1

2 ( )

1 + + + +

⋅ ⋅ + − − ⋅

k k k k

1 2 1 2 1 2 1

2 1 ( 2 1

) ( mod );

Q Q p

z z z

≡ = p –

Ovvero: 1 2 1

2

In questo caso l‘algoritmo della esponenziazione modulare, sarà usato più volte.

Anche per un primo p della forma 4k +1 esiste una formula [Cip] per il valore risolutivo di z, previo il

calcolo di un qualsiasi non residuo quadratico di p. Per la sua espressione si rimanda a [Cip],Dic]. E’ però da

chiarire che l’impiego di tale formula riportata comunque qui di seguito risulta conveniente solo se, posto p

r

2

p = h· 1 :

sotto la forma + , l’esponente r è di valore non grande

r

− +

p 1 2 −

( 1 )

s p

+

r 1

Q −

r 1

2 − r

2 1 Q 2

∑

⋅

≡

z (mod p )

−

r 2 + −

s p

( 2 1 )( 1 )

2 =

s 0 −

r

nr 1

2

r

2

nr p 2 p – 1

e

dove è un qualsiasi non residuo quadratico di è la massima potenza di che divide

2

In questo articolo si vuole mostrare un algoritmo che si basa sull’utilizzo delle Sequenze di Lucas per la

2 ≡ Q (mod p) con p primo di qualsiasi forma .

risoluzione della congruenza z

Prima però di entrare in merito all’algoritmo è opportuno dare qualche cenno nei riguardi di queste sequenze.

Sequenze di Lucas [Rie], [Rib], [SI3] 2

Detti P, Q due numeri interi diversi da zero si consideri la forma quadratica x + P·x + Q = 0

= −

2

D P 4

Q

che prende il nome di equazione caratteristica: il suo discriminante è

Si prendano in esame due successioni o sequenze di numeri interi, una il cui termine generico sarà indicato

con U(k), l’altra con il termine generico V(k), dove k = 0,1,2 3 ….. è l’indice che individua la posizione dei

numeri U e V nella successione.

I primi due termini relativi alla sequenza dei numeri U(k) siano U(0) = 0, U(1) = 1 e per la sequenza

dei numeri V(k), V(0) = 2, V(1) = P

inoltre per ogni k ≥ 2 si ponga: U(k) = P·U(k -1) – Q·U(k-2) (1)

V(k) = P·V(k -1) – Q·V(k-2) (2)

La sequenza dei numeri V(k) prende il nome di sequenza associata (companion) a quella dei numeri U(k).

In un precedente articolo dedicato tali tipi di sequenze [Teo] si era accennato a queste sequenze numeriche;

allora si erano illustrate solo due particolari sequenze tra loro associate e precisamente la successione dei

Numeri di Fibonacci e la successione dei Numeri di Lucas che si ottengono con le regole generali indicate

sopra e ponendo P = 1 e Q = –1. 2

Qui nell’utilizzo delle sequenze di Lucas per trovare le soluzioni della congruenza z ≡ Q (mod p) se

esistono, dobbiamo considerarle in modo più generale, vale a dire con il termine noto qualsiasi Q della

congruenza pari al valore Q dell’equazione caratteristica e con un opportuno P che può avere valore diverso

da 1 e del quale parleremo più avanti. 2

Algoritmo per la risoluzione di z ≡ Q (mod p)

La possibilità di impiegare le sequenze di Lucas per risolvere la congruenza si basa su quanto segue [Rie],

[Rob]: 2

“Data la congruenza z ≡ Q (mod p), se essa è risolubile, prese in considerazione le due sequenze di

2 Q Q

+ P·x + = 0 con = Q e P scelto

Lucas U(k) e V(k) derivate dall’equazione caratteristica x L L V (k )

2

P – 4·Q sia un non residuo quadratico di p, si dimostra che i valori ± (mod p)

in modo che 2

+

p 1 sono le soluzioni cercate della congruenza.

con indice k = 2

Per quanto riguarda i valori U(k) si trova che per tale indice il valore U(k) risulta congruo a 0 (mod p),

cioè U(k) ≡ 0 (mod p) .”

La condizione che il valore U(k) ≡ 0 (mod p) può essere presa come prova,non assoluta comunque, che i

+

p

V (k ) 1

(mod p) con indice k = , sono effettivamente validi.

valori trovati ± 2 2

Vediamo ora quali sono i diversi passi con cui procedere per poter risolvere efficacemente la congruenza:

a) – prima di introdurre il numero p si deve controllare che esso sia effettivamente un numero primo;

b) – si deve verificare che q e p , qualora sia q > 2p, siano primi fra loro;

c) – si deve appurare quindi che la congruenza ammette soluzioni: si dimostra [Tch],[Cip],[Hur] che

−

1

p

z z z 2

essa ha due soluzioni e = p – , se Q è residuo quadratico di p, vale a dire se Q ≡ +1 (mod p);

1 2 1 −

1

p

2

se Q risulta un non residuo quadratico di p, cioè se Q ≡ –1 (mod p) la congruenza non ha soluzioni e

la ricerca ha termine. 3

La verifica che il numero Q sia residuo quadratico o meno di p viene effettuata calcolando il simbolo di

il simbolo di Legendre,

Jacobi [Cip], [Tch], [SI1], [SI2], che in questo caso essendo p primo, coincide con

−

1

p

⎛ ⎞ ⎛ ⎞ ⎛ ⎞

Q Q Q

⎜ ⎟ ⎜ ⎟ ⎜ ⎟

2

ed è indicato come segue : . Si ha pertanto = Q (mod p) e quindi: se ≡ +1 Q è

⎜ ⎟ ⎜ ⎟ ⎜ ⎟

p p p

⎝ ⎠ ⎝ ⎠ ⎝ ⎠

⎛ ⎞

Q

⎜ ⎟ ≡ –1 Q è non residuo quadratico di p.

residuo quadratico di p ; se ⎜ ⎟

p

⎝ ⎠ 2 non

d) – si deve poi trovare un opportuno minimo valore di P tale per cui D = P – 4·Q sia un

⎛ ⎞

D

⎜ ⎟

residuo quadratico di , cioè ≡ –1 (mod p).

p ⎜ ⎟

p

⎝ ⎠ V k

( )

e ) – effettuati questi calcoli occorre trovare un valido algoritmo per calcolare il valore ± (mod p)

2

+

p 1

dove k = utilizzando però formule diverse dalle (1) e (2) in quanto con esse si dovrebbero calcolare

2 +

p 1 ) il che, come già appurato nell’articolo citato,

tutti i valori di U e di V precedenti il valore V ( 2

allungherebbe di molto il tempo di esecuzione.

Il programma scritto in linguaggio Qbasic riportato nell’Allegato 1 comprende i vari punti sotto elencati, ad

esclusione del punto a), ciascuno dedicato a sviluppare algoritmi preposti a risolverli .

Si elencano qui di seguito i diversi algoritmi che devono essere preventivamente utilizzati nel programma

prima di arrivare a quello di cui al punto e).

Punto a) - è opportuno controllare preventivamente che il numero p sia effettivamente primo: solo se p è

primo si procederà ad introdurlo; si prosegue quindi nella costruzione dell’algoritmo per soddisfare quanto

richiesto al punto b).

Punto b) - per verificare che il termine noto Q ed il modulo p siano primi tra loro si controlla che il loro

Massimo Comun Divisore (mcd) abbia valore 1. Si può però evitare il calcolo del (mcd ), anche se non

oneroso, osservando che nell’effettuare al punto c) il calcolo del simbolo di Jacobi., se si trovasse per tale

simbolo il valore 0 (zero), ciò indicherebbe che i numeri Q e p non sono primi fra loro.

⎛ ⎞

Q

⎜ ⎟

Punto c) - per trovare il valore del simbolo di Jacobi: non conviene procedere con il metodo ovvio

⎜ ⎟

p

⎝ ⎠

−

1

p

2 (mod p), ma con un algoritmo alternativo che

di esponenziazione modulare per calcolare il valore Q

consente di arrivare al risultato molto più velocemente. Questo algoritmo si basa sulle cinque seguenti

proprietà e relazioni: c1), c2), c3), c4) c5), attinenti il simbolo di Jacobi [Cip], [SI1,[SI2]:

2 −

− − 1

p

1 1

Q p

⎛ ⎞ ⎛ ⎞ ⎛ ⎞

Q p 2

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 8

2 2

c1: = (-1 ) c2: = (-1)

⎜ ⎟ ⎜ ⎟ ⎜ ⎟

p Q p

⎝ ⎠ ⎝ ⎠ ⎝ ⎠ −

p 1

⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞

−

Q r 1 1

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 2

c3 : = se Q ≡ r ( mod p) c4: = 1 c5: = (-1 )

⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟

p p p p

⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠

Punto d) - per la ricerca dell’ appropriato minimo valore di P si sfrutta lo stesso algoritmo di cui al punto

c) aggiungendo tuttavia nel programma da realizzare opportune istruzioni per tenere conto che occorrerà

ricercare il valore di P tramite anche diverse iterazioni da effettuarsi sull’algoritmo stesso.

Punto e) - Oggetto principale del presente articolo è quello di illustrare un algoritmo atto al calcolo rapido di

un qualsiasi valore V(k) (mod p) della sequenza di Lucas, relativa ai suddetti valori di Q e di P. In

V k

( ) (mod p) per un indice

particolare si deve predisporre un efficiente algoritmo relativo al calcolo di ± 2

4

+

p 1

k = . Non essendo opportuno, come già accennato, ricorrere all’uso delle relazioni (1) e (2) è necessario

2

rivolgere l’attenzione ad altre formule relative ai termini U(k) e V(k) .

Sussistono in effetti le seguenti relazioni [Rib] [SI3] tra i valori delle due sequenze :

U(2·k) = U (k)·V(k) (3)

2 k

– 2·Q (4)

V(2·k) = V(k)

2·U(2·k+1) = U(2·k)·V(1) + V(2k)·U(1) (5)

2·V(2·k+1) = V(2·k)·V(1) +D·U(2·k)·U(1) (6)

dove con k si intende il generico indice. Poiché U(1) = 1 e V(1) = P , tenendo conto delle relazioni (3)

e (4, le due relazioni (5) e (6) si possono scrivere come segue:

2 k

– 2·Q (7)

2·U(2·k+1) = P · U (k) · V(k) + V(k)

2 k

2·V(2·k+1) = P · V(k) + D · U (k) · V(k) – 2·P·Q (8)

2 – 4·Q.

dove, ricordiamo, D =P

Dalle suddette relazioni si constata che valori di U(k) e V(k) ricavati dalle (3) e (4) relativi ad un

generico indice pari 2·k , e dalle (7) e (8) relativi ad un generico indice dispari 2·k +1 dipendono

unicamente dall’indice k e dai valori assunti da U e da V relativi a tale indice k. k

Dall’attenta osservazione dei valori degli indici riportati nel