Residuo potenza n-esima

Un intero a è residuo di potenza k-esima modulo un primo p quando esiste un intero x tale che x elevato a k sia congruente ad a modulo p. Questa domanda generalizza la residualità quadratica (il caso k uguale a due) a cubi, potenze superiori ed esponenti positivi arbitrari usati nella teoria dei numeri da gara e nella crittografia introduttiva. Questa capacità riceve un candidato a, un esponente positivo k e un modulo primo p, riduce a nell'intervallo da zero a p meno uno, verifica che p sia primo e applica il criterio standard del gruppo ciclico sul gruppo moltiplicativo del campo con p elementi. Quando a è divisibile per p la risposta è sempre affermativa per k almeno uno, perché zero a qualsiasi potenza positiva è zero.

Cosa significa un residuo di potenza k-esima modulo un primo

Fissi un modulo primo p e un intero positivo k. Le classi di residuo modulo p formano un campo e i suoi elementi non nulli formano un gruppo moltiplicativo ciclico di ordine p meno uno. Un intero a non divisibile per p è residuo di potenza k-esima modulo p proprio quando a appartiene all'immagine della mappa che invia ogni classe non nulla x a x elevato a k.

Poiché il gruppo è ciclico, quell'immagine è l'unico sottogruppo di indice uguale al massimo comun divisore d di k e p meno uno, e a appartiene a quel sottogruppo se e solo se a elevato alla potenza (p meno uno) divisa per d è congruente a uno modulo p. Quell'unica esponenziazione modulare è la procedura di decisione usata qui.

Quando a è divisibile per p, la congruenza x alla k congruente ad a ha la soluzione banale x congruente a zero per ogni k almeno uno, così zero è sempre trattato come residuo di potenza k-esima. I casi speciali recuperano strumenti noti: per k uguale a due e p primo dispari il criterio è quello di Eulero per la residualità quadratica, la stessa informazione del simbolo di Legendre, mentre per k uguale a p meno uno ogni a non nullo è residuo per il piccolo teorema di Fermat.

Contratto di ingresso, controllo di primalità e campi di risposta

Invii gli interi a, k e p. L'esponente k deve essere almeno uno e al massimo un bilione (10^12). I nomi di campi opzionali non vengono mai riempiti con null: la coppia di criterio è semplicemente omessa nel caso di residuo zero.

Controlli classici che Lei può riprodurre a mano: per a uguale a due, k uguale a tre e p uguale a sette, il gcd di tre e sei è tre, quindi l'esponente di criterio è due e due al quadrato è quattro modulo sette, non uno; pertanto due non è residuo cubico modulo sette; al contrario uno è sempre residuo di potenza k-esima per ogni primo perché uno a qualsiasi potenza è uno.

Non interi, campi obbligatori mancanti ed esponenti sotto uno falliscono la validazione con un messaggio chiaro in inglese.

Dove compaiono i controlli di residui di potenze superiori nel lavoro reale

I programmatori da gara hanno bisogno di un oracolo rapido prima di tentare di estrarre radici cubiche modulari o di ordine superiore: se il bit di residuo è falso non ha senso cercare x. Gli studenti di crittografia verificano esercizi sull'immagine della mappa potenza nei campi finiti, esempi di calcolo dell'indice e costruzioni didattiche che dipendono dal fatto che una classe di messaggio sia una potenza k-esima prima di applicare una mappa.

Le pipeline di ricerca e compiti che già usano i simboli di Legendre o Jacobi per i quadrati spesso necessitano della stessa risposta sì o no per cubi e potenze superiori senza cambiare libreria. Se Le serve solo la residualità quadratica, restano disponibili gli strumenti dedicati di residuo quadratico e simbolo di Legendre; questa pagina è la decisione generale di potenza k-esima per moduli primi.