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

Un algoritmo per la risoluzione della congruenza quadratica z ≡ Q (mod p)

Cristiano Teodoro

teodorocristiano@tiscali.it 2

(An algorithm for solution of quadratic congruences z ≡ Q (mod p)

2

Sommario

In questo articolo viene descritto un algoritmo per risolvere le congruenze quadratiche con modulo primo p di qualsiasi forma in modo molto più veloce ed efficace rispetto al banale algoritmo esaustivo. L’algoritmo proposto si basa sulle proprietà delle sequenze di Lucas. Dopo una breve premessa dedicata a chiarire il significato di congruenza e alla esposizione di formule risolutive per congruenze con moduli primi di forma particolare, vengono illustrate le sequenze di Lucas e le loro principali proprietà. Si passa quindi ad illustrare l’algoritmo la cui comprensione e realizzazione tocca sia argomenti della teoria dei numeri, quali le proprietà attinenti le congruenze, le cognizioni sui residui quadratici e non quadratici con una applicazione riguardante un efficiente algoritmo di calcolo del simbolo di Jacobi, sia l’utilizzo di originali formule di tipo iterativo per il calcolo di U(k) e V(k), previa la generazione di una conveniente successione dei loro indici. Per una migliore comprensione dell’algoritmo esposto si illustra una sua applicazione con un esempio che implica per ovvie ragioni di spazio valori numerici per Q e p costituiti da poche cifre.

L’importanza di avere disponibile un algoritmo per una rapida e fattiva risoluzione di congruenze quadratiche con modulo p primo risulta evidente quando si pensi che il suo utilizzo è fondamentale ed indispensabile in uno dei più efficienti moderni metodi di fattorizzazione di un numero grande, il metodo del Crivello Quadratico (Quadratic Sieve). In allegato (Allegato 1) è dato il listato in linguaggio Qbasic dell’algoritmo esposto riguardante congruenze quadratiche con valori del termine noto Q limitato a valori numerici costituiti al massimo da 15 cifre e a valori del modulo p con non più di 8 cifre, condizionamento questo dovuto alle limitazioni di precisione di calcolo della aritmetica a doppia precisione disponibile sul PC. L’algoritmo esposto si presta bene ad una sua programmazione con una aritmetica a precisione multipla in modo di poter trattare congruenze aventi termine noto Q sia positivo che negativo e modulo p primo grandi, costituiti anche da centinaia di cifre. E’ stato realizzato pertanto un più complesso programma sempre in Qbasic dove tutti i calcoli vengono realizzati in aritmetica a precisione multipla. Con tale programma si possono ottenere delle prestazioni di tempi di risoluzione estremamente più brevi rispetto a quelli ottenibili con un programma relativo al banale algoritmo esaustivo di risoluzione della congruenza. Non si è ritenuto opportuno allegare al presente articolo il suo listato, data la sua non indifferente lunghezza. Si allega invece una Tabella che riporta, ottenuti con tale programma, alcuni risultati di soluzioni di congruenze con valori sia piccoli che grandi di Q e di p con i tempi di calcolo riferibili ai due tipi di algoritmi: quello illustrato nell’articolo e quello di tipo esaustivo. Si riportano in allegato anche diversi esempi di risultati ottenuti. Vengono infine accennati i campi di applicazione e di utilizzo degli argomenti trattati, che non si limitano al solo campo della matematica, ma che toccano vari campi tecnologici, in particolare quello delle telecomunicazioni e della crittografia.

Abstract

In this paper a fast algorithm for the exact resolution of quadratic congruences modulo any prime is proposed as an alternative to the trivial exhaustive method, very slower for high moduli (primes). The algorithm refers to the Lucas Sequences characteristics. After some preliminary remarks related to explain the congruence meaning and to show solution formulas for congruences with peculiar primes, we illustrate the main characteristics of these sequences. Then we explain the algorithm, whose understanding and implementation involves several elementary topics of the number theory, as the congruence properties, the quadratic and non quadratic residues, with an application pertaining to the Jacobi symbol calculus. So an original use of the U(k) and V(k) recurrence relation is illustrated, by previous production of a suitable sequence of k index. For a better understanding of the algorithm we show an application example with Q and p small values. The consequence of this algorithm is clear for its basic use in connection with the main Quadratic Sieve factorization method. We enclose in this article a program in Qbasic language of the algorithm (Allegato 1), related to quadratic congruences with small values of Q and p input. This restriction is imposed by the use and the limits of double arithmetic precision. But the algorithm is suitable for a multiple precision arithmetic in order to handle congruences with large Q and modulus p, composed by several tens of digits or some hundred of digits. For this reason we have carried out a more complex program still in Qbasic language, but not enclosed to this paper. We achieve with this routine solution times much shorter compared to those realized by the trivial exhaustive algorithm. We report in a Table some examples of quadratic congruences solutions and of their computation times related to current and exhaustive algorithms as well some examples of solutions outputs. In the end we show briefly some technical application of the quadratic residues and quadratic congruence, related to the telecommunications and to the cryptography.

Introduzione

1

Chiariamo innanzitutto il significato dell’espressione z ≡ Q (mod p).

Nel campo della teoria delle congruenze [Tch] le espressioni della forma M ≡ N (mod. A) sono note col nome di congruenze; i numeri interi M ed N si dicono congrui fra loro rispetto al numero A che si chiama modulo della congruenza; detti numeri M ed N possono essere positivi o negativi; in ogni caso la suddetta espressione indica la divisibilità algebrica di M – N per A dove A viene considerato sempre positivo.

2

Nel nostro specifico caso l’espressione z ≡ Q (mod p) è denominata congruenza binomia quadratica e si esprime dicendo che l’incognita z elevata al quadrato è congrua modulo p al termine noto Q.

Con tale dizione si vuole significare che occorre trovare un valore dell’incognita z sempre se esiste, tale per cui il resto della divisione per p di essa elevata al quadrato sia il valore Q. Se la congruenza ha come modulo un numero primo p e risulta risolubile, ammette allora due soluzioni [Tch] ed il valore Q viene chiamato residuo quadratico di p. Se essa non ha soluzioni Q viene chiamato non residuo quadratico di p. Il numero p come già accennato prende il nome di modulo della congruenza. Per ora si prenderanno in considerazione per p solo numeri primi.

Nella letteratura tecnica si conoscono diversi algoritmi [Cip], [Kra], [Rie], [Rob], [Wag] dedicati alla risoluzione della congruenza z ≡ Q (mod p) con p numero primo e Q ≠ 0 intero e primo con p.

2

Quello banale della ricerca esaustiva di z estesa al limite sino al valore p, è senz’altro da scartare per la durata eccessiva di calcolo anche per valori di p non molto grandi. E’ noto poi [Tch] che la risoluzione di tale tipo di congruenza binomia risulta indispensabile per risolvere la congruenza quadratica di forma generale ax² + bx + c ≡ 0 (mod p) dove a, b, c sono degli interi, p è primo, e a è primo con p. In effetti la suddetta congruenza ha soluzioni se e solo se la congruenza binomia z ≡ q (mod p) derivata da essa ponendo z = 2ax + b e q = (b² - 4ac), risulta risolubile.

Inoltre, da quanto si deduce dalla teoria delle congruenze [Tch], appurato che la suddetta congruenza binomia z² ≡ q è risolubile e chiamate z₁ e z₂ le sue due soluzioni, valgono le due seguenti congruenze lineari: 2ax₁ + b ≡ z₁ (mod p); 2ax₂ + b ≡ z₂ (mod p) nelle incognite x₁ e x₂ che, una volta trovate, risultano essere le due soluzioni della congruenza quadratica ax² + bx + c ≡ 0 (mod p).

Esistono vari noti algoritmi, come ad esempio quello ideato da Eulero [Eul] o quello basato sulle frazioni continue [Old], [Te1] per risolvere una congruenza lineare, su cui non è il caso qui di soffermarsi.

2

Congruenze con moduli primi di forma particolare

La risoluzione della z² ≡ Q (mod p) tramite algoritmi più o meno semplici dipende inoltre dalla forma di p: se tale primo è della forma 4k + 3 è ben noto [Tch], [Rie] che i due valori di z soddisfacenti la congruenza, previa verifica della loro esistenza, sono dati dal resto della divisione di Q^k+1 per p, vale a dire z₁ ≡ Q^k+1 (mod p) e z₂ = p – z₁. Il calcolo di z₁ può essere pertanto effettuato con un efficiente 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].

Nel caso poi in cui il primo p è della forma 8k + 5 le soluzioni della congruenza sono le seguenti [Cip]:

p¹

z₁ ≡ Q · (Q^(p+3)/8 + 1 - (Q^(p-1)/4 · Q)^(p-5)/8) (mod p); z₂ = p – z₁.

Ovvero:

z₁ ≡ Q^(k+1)/2 (2Q^k+1 - 1)² (mod p); z₂ = p – z₁.

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 sotto la forma 2^r · h + 1, l’esponente r è di valore non grande:

p – 1 = 2^r · s

z ≡ Q^((s+1)/2) · ∑ (Q^2s)ⁿ (mod p)

dove s è un qualsiasi non residuo quadratico di p e 2^r è la massima potenza di 2 che divide p – 1.

Sequenze di Lucas

In questo articolo si vuole mostrare un algoritmo che si basa sull’utilizzo delle Sequenze di Lucas per la risoluzione della congruenza z² ≡ Q (mod p) con p primo di qualsiasi forma.

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 che prende il nome di equazione caratteristica: il suo discriminante è D = P² – 4Q.

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.

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.

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]:

“Data la congruenza z² ≡ Q (mod p), se essa è risolubile, prese in considerazione le due sequenze di Lucas U(k) e V(k) derivate dall’equazione caratteristica x² + P·x + Q = 0 con Q = Q e P scelto in modo che P² – 4·Q sia un non residuo quadratico di p, si dimostra che i valori ± V(k)/2 (mod p) con indice k = (p + 1)/2 sono le soluzioni cercate della congruenza.

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 valori trovati ± V(k)/2 (mod p) con indice k = (p + 1)/2, sono effettivamente validi.

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 essa ha due soluzioni z₁ e z₂ = p – z₁, se Q è residuo quadratico di p, vale a dire se Q^{(p – 1)/2} ≡ +1 (mod p); se Q risulta un non residuo quadratico di p, cioè se Q^{(p – 1)/2} ≡ –1 (mod p), la congruenza non ha soluzioni e la ricerca ha termine.

La verifica che il numero Q sia residuo quadratico o meno di p viene effettuata calcolando il simbolo di Jacobi [Cip], [Tch], [SI1], [SI2], che in questo caso essendo p primo, coincide con il simbolo di Legendre, ed è indicato come segue:

(Q / p) = Q^{(p – 1)/2} (mod p) e quindi: se (Q / p) ≡ +1 Q è residuo quadratico di p; se (Q / p) ≡ –1 Q è non residuo quadratico di p.

• D) Si deve poi trovare un opportuno minimo valore di P tale per cui D = P² – 4·Q sia un non residuo quadratico di p, cioè (D / p) ≡ –1 (mod p).
• E) Effettuati questi calcoli occorre trovare un valido algoritmo per calcolare il valore ± V(k)/2 (mod p) dove k = (p + 1)/2 utilizzando però formule diverse dalle (1) e (2) in quanto con esse si dovrebbero calcolare tutti i valori di U e di V precedenti il valore V((p + 1)/2), il che, come già appurato nell’articolo citato, 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.

Punto c)

Per trovare il valore del simbolo di Jacobi:

(Q / p)

non conviene procedere con il metodo ovvio di esponenziazione modulare per calcolare il valore Q^{(p – 1)/2} (mod p), ma con un algoritmo alternativo che 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]:

c1: (Q / p) = (p / Q) (-1)^{((p-1)/2)((Q-1)/2)}

c2: (2 / p) = (-1)^(p2-1)/8

c3: (Q / p) = (r / p) se Q ≡ r (mod p)

c4: (1 / p) = 1

c5: (Q / p) = (-1)^(Q-1)/2

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 particolare si deve predisporre un efficiente algoritmo relativo al calcolo di ± V(k)/2 (mod p) per un indice k = (p + 1)/2.