Roots of a polynomial mod a prime

Question

Sto cercando un algoritmo veloce per trovare le radici di un polinomio univariato in un campo finito primario.

Cioè, se f = a0 + a1x + a2x2 + ... + anxn (n> 0) quindi un algoritmo che trova tutto r < p soddisfacente f(r) = 0 mod p, per un dato primo p.

Ho trovato l'algoritmo di ricerca di Chiens https://en.wikipedia.org/wiki/Chien_search ma non posso immaginare che sia così veloce per i numeri primi di 20 bit. Qualcuno ha esperienza con l'algoritmo di ricerca di Chien o conosce un modo più veloce? C'è un modulo sympy per questo?

Answer 1

Questo è abbastanza ben studiato, come indica il commento di mcdowella. Ecco come il Cantor-Zassenhaus random algorithm funziona per il caso in cui si desidera trovare le radici di un polinomio, invece della fattorizzazione più generale.

Si noti che nell'anello di polinomi con coefficienti mod p, il prodotto x (x-1) (x-2) ... (x-p + 1) ha tutte le possibili radici e uguale a x^px di Fermat's Little Theorem e una fattorizzazione unica in questo anello.

Set g = GCD (f, x^p-x). L'uso di Euclid's algorithm per calcolare il GCD di due polinomi è in generale veloce, prendendo un numero di passaggi logaritmico nel grado massimo. Non richiede di calcolare i polinomi. g ha le stesse radici di f sul campo e nessun fattore ripetuto.

Grazie alla particolare forma di x^px, con solo due termini non nulli, il primo passo dell'algoritmo di Euclide può essere fatto da repeated squaring, in circa 2 log_2 (p) operazioni che coinvolgono solo polinomi di grado non più di due volte la grado di f, con coefficienti mod p. Possiamo calcolare x mod f, x^2 mod f, x^4 mod f, ecc., Quindi moltiplicare insieme i termini corrispondenti a posti diversi da zero nell'espansione binaria di p per calcolare x^p mod f, e infine sottrarre x.

Fare ripetutamente quanto segue: Scegliere un d casuale in Z/p. Calcola il GCD di g con r_d = (x + d)^((p-1)/2) -1, che riusciamo a calcolare rapidamente dall'algoritmo di Euclide, usando il quadrato ripetuto sul primo gradino. Se il grado di questo GCD è strettamente compreso tra 0 e il grado di g, abbiamo trovato un fattore non banale di g, e possiamo recurse fino a quando non abbiamo trovato i fattori lineari quindi radici di g e quindi f.

Quanto spesso funziona? r_d ha come radici i numeri che sono d minori di un quadrato diverso da zero p. Considera due radici distinte di g, aeb, quindi (x-a) e (x-b) sono fattori di g. Se + d è un quadrato diverso da zero e b + d non lo è, allora (xa) è un fattore comune di g e r_d, mentre (xb) non lo è, il che significa che GCD (g, r_d) è un fattore non banale di g . Allo stesso modo, se b + d è un quadrato diverso da zero mentre un + d non lo è, allora (x-b) è un fattore comune di g e r_d mentre (x-a) non lo è. Con la teoria dei numeri, un caso o l'altro accade vicino alla metà delle possibili scelte per d, il che significa che in media richiede un numero costante di scelte di d prima di trovare un fattore non banale di g, in realtà uno che separa (xa) da (xb).

Answer 2

Le tue risposte sono buone, ma penso di aver trovato un metodo meraviglioso per trovare le radici modulo qualsiasi numero: Questo metodo basato su "LATTICES". Let r ≤R essere una radice di mod p . Dobbiamo trovare un'altra funzione come h (x) tale che h non è grande e r è radice di h. Il metodo Lattice trova questa funzione.Per la prima volta, dobbiamo creare una base polinomiale per il reticolo e quindi, con l'algoritmo "LLL", troviamo un "vettore più breve" che ha radice r senza modulo p. Infatti, eliminiamo il modulo p in questo modo.

Per ulteriori spiegazioni, fare riferimento a "Coppersmith D. Ricerca di piccole soluzioni per polinomi di piccolo grado In crittografia e reticoli".