Multiplication rapide dans Z/pZ[X]

Lulye · May 2017

Bonjour,
Je cherche un algorithme me permettant de multiplier rapidement deux polynômes à coefficients dans Z/pZ.
J'ai déjà implémenté l'algorithme de Karatsuba, et une transformée de [large]F[/large]ourrier rapide classique. Seul problème, Z/pZ ne contient pas toujours de racine primitive n-ième de l'unité. Pour palier à cela, j'ai vu l'algorithme de Schohange et Strassen, mais je ne le comprends pas bien, et je ne suis pas sûre qu'il soit adapté à mon cas.
J'aurais donc besoin d'une technique de multiplication qui aurait une bonne complexité pour tout p premier à trois chiffres (je ne devrais pas avoir besoin d'entiers au-dessus de 1000). Si quelqu'un a des idées, je lui en serais très reconnaissante.
Merci d'avance,
Lulye

[Joseph Fourier (1768-1830) prend toujours une majuscule. AD]

parisse · June 2017

Vous pouvez reduire modulo p le produit dans Z[X], produit calcule avec les restes chinois du produit par fft modulo 2 premiers bien choisis.
Par exemple si la somme des degres est strictement inferieure a 2^26 (environ 67 millions):
p1 := 2013265921=(15*2^27+1) ; r:=1227303670; root of unity order 2^27
p2 := 1811939329 ; r:=814458146; order 2^26

fluorhydrique · July 2017

édit : mince! Fourier un seul r

Bonjour

J'ai déjà implémenté ...et une transformée de Fourier rapide classique. Seul problème, Z/pZ ne contient pas toujours de racine primitive n-ième de l'unité.

::o

il semble que tu n'ai pas compris le principe de la transformée de Fourier
(et du coup ni non plus la rapide)

entre parenthèses tu comprendra la rapide si tu comprend d'abord comment fonctionne la transformée de Fourier et je te soupçonne d'avoir zappé un truc

Tout repose sur le choix d'une racine primitive n-ième de l'unité qui en dehors de la grandeur adéquate de n pour ton calcul se fiche complètement des paramètres à calculer

Poirot · July 2017

@fluorhydrique : sauf que si de telles racines n'existent pas on est un peu embêté...

Multiplication rapide dans Z/pZ[X]

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 1