Radice n-esima modulare

Una radice k-esima modulare di un intero a modulo un primo p è ogni residuo x tale che x elevato a k sia congruente ad a modulo p. Le radici quadrate modulo primi compaiono nei tutorial di Tonelli–Shanks, le radici cubiche e di ordine superiore nell’algebra dei campi finiti, e i corsi di crittografia necessitano di un oracolo affidabile che elenchi ogni radice oppure rifiuti con chiarezza quando nessuna esiste. Questo calcolatore accetta a, un esponente positivo k e un modulo primo p, riduce a nell’intervallo canonico da zero a p meno uno e restituisce l’elenco ordinato completo delle soluzioni in quel campo.

Cosa sono le radici k-esime modulari e quando esistono

Nel gruppo moltiplicativo di un campo primo ogni residuo non nullo ha un ordine ben definito che divide p meno uno. Elevare x alla k produce una mappa la cui immagine è l’insieme dei residui potenza k-esima. Per un obiettivo a non nullo la congruenza x alla k congruente ad a modulo p ha soluzioni se e solo se a elevato a (p meno uno) diviso d è congruente a uno, dove d è il massimo comun divisore di k e p meno uno.

Quando il criterio vale ci sono esattamente d radici non nulle distinte. Il residuo zero è speciale: zero a ogni potenza positiva è zero, quindi a congruente a zero ha la sola radice zero. I moduli composti escono da questo quadro di gruppo ciclico e vengono rifiutati affinché il solver non finga mai che un prodotto tramite il teorema cinese del resto sia una risposta di campo primo.

Gli studenti incontrano le radici quadrate controllando a mano i simboli di Legendre, le radici di ordine superiore studiando coset ciclotomici o logaritmi discreti, e i fallimenti di esistenza quando un compito chiede la radice cubica di un non residuo cubico.

Come questo calcolatore trova ogni radice

Chiami la capacità con i campi interi a, k e p. L’implementazione verifica prima che k sia un intero positivo e che p sia un primo entro il limite pubblicato mediante un test di Miller–Rabin deterministico. Dopo aver ridotto a modulo p, il caso di residuo zero restituisce la sola radice zero.

Per a non nullo calcola d uguale all’mcd di k e p meno uno e applica il test di esistenza sopra. Quando d vale uno c’è un’unica radice ottenuta elevando a all’inverso modulare di k modulo p meno uno, il percorso veloce per esponenti coprimi. Quando d è maggiore di uno il solver trova una radice primitiva g modulo p, recupera il logaritmo discreto di a in base g con baby-step giant-step e risolve la congruenza lineare k per y congruente a quel logaritmo modulo p meno uno.

Ogni radice restituita è verificata mediante esponenziazione modulare prima dell’emissione della risposta. I valori assoluti di a e k sono limitati a un bilione e il primo p vicino a un miliardo affinché la memoria di baby-step giant-step resti pratica; se d superasse diecimila radici la richiesta viene rifiutata anziché inondare il client.