Radice quadrata modulare di Cipolla

L'algoritmo di Cipolla è un metodo classico della teoria dei numeri per estrarre radici quadrate modulo un primo dispari. Dati un intero a e un primo dispari p, restituisce un intero x tale che x al quadrato sia congruente ad a modulo p quando a è un residuo quadratico. I compiti di crittografia, la programmazione competitiva e i tutorial di aritmetica modulare spesso necessitano della radice esplicita — non solo del test sì o no di residualità del simbolo di Legendre.

Cos'è una radice quadrata modulare e quando si applica Cipolla

Nell'aritmetica modulare la congruenza x al quadrato congruente ad a modulo p chiede un intero x il cui quadrato cada nella stessa classe di residuo di a. Quando p è un primo dispari la risposta teorica è nitida: o a è divisibile per p e l'unica radice è zero, oppure esattamente metà delle classi non nulle sono residui quadratici e ogni residuo ha esattamente due radici r e p meno r. Il simbolo di Legendre indica in quale caso si trova, ma non costruisce r.

L'algoritmo di Cipolla colma quel divario lavorando in un'estensione quadratica scelta del campo con p elementi. Si sceglie un intero ausiliario omega tale che omega al quadrato meno a sia un non residuo quadratico modulo p; allora l'elemento omega più una radice quadrata formale di quel non residuo, elevato alla potenza (p più uno) divisa per due, ricade nel campo base e uguaglia una radice quadrata di a. Fallisce anche quando p è composto o pari, perché l'algoritmo classico e il criterio di Eulero assumono un modulo primo dispari.

Rispetto a Tonelli–Shanks, Cipolla è spesso più breve da implementare per demo didattiche e primi di media dimensione, e non richiede di fattorizzare p meno uno. Questa capacità si rivolge quindi a studenti, docenti e script che vogliono un percorso Cipolla trasparente con radici ordinate stabili e un contratto di errore documentato.

Dove le radici quadrate modulari di Cipolla creano valore

Le piattaforme di contest e i correttori LMS necessitano di un oracolo deterministico che rifiuti non residui e moduli composti invece di restituire array vuoti che un client difettoso potrebbe trattare come successo. Le note di crittografia che introducono la cifratura Rabin o la decompressione di punti su campi primi spesso vogliono un percorso Cipolla accanto a Tonelli–Shanks; un modulo puro condiviso mantiene identiche demo del browser e controlli del server.

Mantenga p entro il limite primo pubblicato, fissi l'array di radici ordinate nei test, e ottiene radici quadrate modulari riproducibili per didattica, automazione e edge workers senza incorporare un intero stack di algebra computazionale.