Calcolatore radice primitiva

Una radice primitiva modulo un primo p è un generatore del gruppo moltiplicativo dei residui diversi da zero modulo p. In termini semplici, qualche intero g tra 1 e p meno uno ha la proprietà che le sue potenze successive g, g al quadrato, g al cubo, e così via, alla fine toccano ogni classe di resto coprima con p prima di ripetersi. Quel g è un generatore di (Z/pZ)*, e il più piccolo g positivo di questo tipo è la classica risposta di teoria dei numeri che studenti, crittografi e risolutori di gare cercano. Questo calcolatore prende un modulo primo p, verifica che p sia primo, fattorizza p meno uno, e restituisce la radice primitiva minima insieme all'ordine del gruppo e alla fattorizzazione in potenze prime di p meno uno. Il percorso è completamente deterministico: Miller-Rabin con insiemi di testimoni fissi, fattorizzazione per tentativi ed esponenziazione modulare senza rete, senza casualità e senza dipendenza dalla data.

Cos'è una radice primitiva e cosa contiene la risposta

Per un modulo primo p, l'insieme dei residui 1, 2, …, p meno uno forma un gruppo moltiplicativo ciclico di ordine p meno uno. Un intero g è una radice primitiva modulo p quando l'ordine di g in quel gruppo è esattamente p meno uno: le potenze g elevato a k per k da 0 fino a p meno due sono tutte distinte modulo p ed esauriscono ogni resto diverso da zero.

Non ogni intero è un generatore; per esempio modulo 7 le potenze di 2 ciclano solo attraverso tre valori prima di ripetersi, quindi 2 non è una radice primitiva, mentre 3 genera tutte e sei le unità ed è la più piccola. Non c'è alcuna congettura probabilistica presentata come radice e nessun ripiego silenzioso per moduli composti, perché una radice primitiva in senso classico è definita per i primi (e alcune famiglie composte speciali che questa pagina non copre).

Se ti servono i fattori di un intero arbitrario invece di un generatore mod p, usa invece una capacità di fattorizzazione; questa pagina risponde solo alla domanda sul generatore minimo mod primo.

Come viene verificato il primo e come si trova la radice minima

Il segno più iniziale opzionale è ammesso; spazi incorporati, prefissi esadecimali e notazione esponenziale vengono respinti con un messaggio chiaro, così che una cella sbagliata non diventi un generatore errato. Dopo l'interpretazione, il motore esegue un test di primalità Miller-Rabin deterministico con insiemi di testimoni dimostrati sufficienti per ogni intero fino a quindici cifre decimali.

Quando p è primo, il motore fattorizza p meno uno tramite divisione per tentativi con ruota, raccoglie i fattori primi distinti q di quell'ordine, e cerca g uguale a 2, 3, 4, … per il primo candidato tale che g elevato a (p meno uno) diviso q non sia congruo a 1 modulo p per ogni tale q. Quel criterio classico è necessario e sufficiente affinché g abbia ordine p meno uno. Il caso speciale p uguale a 2 restituisce radice primitiva 1, l'unica unità in quel gruppo.

Dove si usano le radici primitive minime nello studio, nella crittografia e nel codice

Gli studenti incontrano le radici primitive quando imparano i gruppi ciclici, i logaritmi discreti e la struttura dei campi finiti di ordine primo. Le schede di esercizi spesso chiedono il generatore minimo modulo un piccolo primo; questa pagina restituisce quella risposta con la fattorizzazione di supporto di p meno uno così puoi verificare a mano i test dell'ordine.

I problemi di gara e gli enunciati di kata di programmazione richiedono spesso la radice primitiva minima come subroutine per costruire polinomi primitivi, indicizzare tabelle di logaritmo discreto o inizializzare dimostrazioni di teoria dei numeri.

Nella crittografia applicata, Diffie-Hellman e costruzioni correlate hanno bisogno di un generatore di un grande sottogruppo di ordine primo; mentre i sistemi di produzione usano primi sicuri accuratamente scelti e generatori standardizzati, un calcolatore trasparente per primi ordinari è comunque utile quando validi parametri su scala da compiti a casa, scrivi test unitari per helper dell'ordine modulare, o spieghi perché g uguale a 2 funziona per alcuni primi e non per altri.