Encontre o restante de um grande polinômio fixo quando dividido por um pequeno polinômio desconhecido

9

Suponha que operemos em um campo finito. Nos é dado um grande polinômio fixo p (x) (de, digamos, grau 1000) sobre esse campo. Esse polinômio é conhecido de antemão e temos permissão para fazer cálculos usando muitos recursos na "fase inicial". Esses resultados podem ser armazenados em tabelas de pesquisa razoavelmente pequenas.

No final da "fase inicial", receberemos um pequeno polinômio desconhecido q (x) (de, digamos, grau 5 ou menos).

Existe uma maneira rápida de calcular p (x) mod q (x), considerando que estamos autorizados a fazer alguns cálculos complicados na "fase inicial"? Uma maneira óbvia é calcular p (x) mod q (x) para todos os valores possíveis de q (x). Existe uma maneira melhor de fazer isso?

paulwaters
fonte

Respostas:

3

Os algoritmos a seguir funcionam bem se o campo subjacente tiver uma ordem muito pequena .s

Suponha que sabemos é irredutível, de grau fixo d . Então, mod q , sabemos que x s d = x é válido. Portanto, basta pré-calcular .qdqxsd=xp(x)modxsdx

Em geral, pode se decompor em um produto de polinômios irredutíveis . Nesse caso, um argumento semelhante se aplica à computação de módulo cada separadamente e, em seguida os resultados. Então, nós realmente precisamos calcular para cada .q(x)q=q1qrpq1,,qrp(x)modxsdxdd

David Harris
fonte
2

Eu acho que existe uma maneira bem rápida de fazer isso. Deixe os coeficientes do polinômio ainda desconhecido sejam , então onde é um número pequeno. Agora vamos começar a calcular onde , onde é grande e são conhecidos. Isso é feito reduzindo o grau usando as como . Eventualmente, obtemos um polinômio grau , cujos coeficientes são polinômios do (desde que oqbiq=i=0dbixidp(modq)p=i=0DaixiDaiaDxD=aDbdi=1d1bdixDi<d1biaisão conhecidos). Podemos calcular rapidamente esses polinômios depois de obtermos .q

domotorp
fonte
-1

Veja excelentes comentários sobre este post abaixo. :)


Pré-processando; entrada: p(x)

  1. Fatore como .p(x)p(x)=i=01000(xiri)

  2. Armazene isso como uma tabela de raízes distintas e suas respectivas multiplicidades .Trjmj

Fase online; entrada: q(x)

  1. Fatore como .q(x)q(x)=i=05(xiri)

  2. Armazene isso como uma lista de raízes distintas e suas respectivas multiplicidades .Lrjmj

  3. Enquanto não está vazia, remover o seguinte raiz / multiplicidade de e qualquer termos semelhantes em .LLT

  4. Leia da tabela modificada e faça a saída.p(x)modq(x)T


Outros comentários:

  • Obviamente, você deseja classificar a tabela e acessá-la com pesquisa binária (ou uma árvore).T
  • (Seja o grau de .) Se você deseja que a saída esteja na representação do coeficiente, você pode fazer várias FFTs no final para obter tempo.dp(x)p(x)modq(x)O~(d)
  • Dependendo de como você o formaliza, provavelmente você pode pré-calcular várias maneiras de recombinar os termos em antes (estilo de programação dinâmica), para que a maioria (ou todas) das multiplicações sejam apenas pesquisas. O custo dominante é então o número de pesquisas, ou aproximadamente . Se , este é apenas um punhado de operações aritméticas concretas.TO(logd)d=1000
Daniel Apon
fonte
2
Em que campo você está considerando p? Qual o tamanho que você espera que essa representação tenha em termos do campo original? E quando você diz para ler da tabela e saída modificadas, o que você quer dizer?
precisa
2
Isso só funcionaria se você estivesse operando em um campo onde e dividem. Mas isso parece depender de ; em particular, você não pode pré-calcular as raízes apenas para . Além disso, calcular as raízes de em um campo tão grande levará tempo (pelo menos); isso não é melhor que o algoritmo ingênuo. pqqpq|p|
David Harris