Essa é uma "questão histórica" mais do que uma questão de pesquisa, mas a redução clássica à busca de ordens no algoritmo de Shor para fatoração foi descoberta inicialmente por Peter Shor, ou era conhecida anteriormente? Existe um artigo que descreva a redução que antecede Shor, ou é simplesmente...
O livro de Arora e Barak apresenta o fatorial como o seguinte problema: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Eles acrescentam, ainda...
Deixe o PRIMES (também conhecido como teste de primalidade ) ser o problema: Dado um número natural , é um número primo?nnnnnn Que FACTORING seja o problema: Dados os números naturais , com , tem um fator com ?nnnmmm1 ≤ m ≤ n1≤m≤n1 \leq m \leq nnnnddd1 < d< m1<d<m1 < d <...
Esta é uma postagem cruzada de math.stackexchange. Deixe FACT denotar o problema de fatoração de número inteiro: dado encontre os números primos e os números inteiros modo quep i ∈ N , e i ∈ N , n = Π k i = 0 p e i i .n ∈ N ,n∈N,n \in \mathbb{N},pEu∈ N ,pi∈N,p_i \in \mathbb{N},eEu∈ N ,ei∈N,e_i...
O fatoramento não é conhecido por ser NP-completo. Esta pergunta pediu consequências do fato de o Factoring ser NP-completo. Curiosamente, ninguém pediu consequências do fato de o Factoring estar em P (talvez porque essa pergunta seja trivial). Então, minhas perguntas são: Qual seria o teórico...
Dado um número inteiro de comprimento bits, quão difícil é produzir o número de fatores primos (ou o número alternativo de fatores) de ?n NNNNnnnNNN Se soubéssemos a fatoração primária de , isso seria fácil. No entanto, se soubéssemos o número de fatores primos ou o número de fatores gerais,...
A postagem no blog de Scott Aaronson hoje deu uma lista de problemas / tarefas abertos interessantes em complexidade. Um em particular chamou minha atenção: Crie uma biblioteca pública de instâncias 3SAT, com o menor número possível de variáveis e cláusulas, que teria consequências notáveis...
Existem referências sobre
Esta questão foi migrada do Computer Science Stack Exchange porque pode ser respondida no Theoretical Computer Science Stack Exchange. Migrou há 3 anos . No artigo científico de 2016 " Realização de um algoritmo Shor escalável " [ 1 ], os autores fatoram 15 com apenas 5...
Estou procurando uma referência para o seguinte resultado: Adicionar dois números inteiros na representação fatorada é tão difícil quanto fatorar dois números inteiros na representação binária usual. (Tenho certeza de que está lá fora, porque isso é algo que eu já tinha pensado em algum...
É sabido que a exponenciação modular (a parte principal de uma operação RSA) é computacionalmente cara e, até onde eu entendi, a técnica da exponenciação modular de Montgomery é o método preferido. A exponenciação modular também é destaque no algoritmo de fatoração quântica, e também é cara...
Em seu artigo de 1995, Algoritmos de tempo polinomial para fatoração primária e logaritmos discretos em um computador quântico , Peter W. Shor discute uma melhoria na parte de busca de pedidos de seu algoritmo de fatoração. As saídas algoritmo padrão , um divisor de ordem de módulo . Em vez de...
Acabei de ler a pergunta " A fatoração inteira é um problema NP-completo? " ... então decidi gastar parte da minha reputação :-) fazendo outra pergunta com P ( Q é trivial ) ≈ 1 :QQQP(Q is trivial)≈1P(Q is trivial)≈1P(\text{Q is trivial}) \approx 1 Se é um oráculo que resolve inteiro fatoração, o...
Ao ler o blog de Dick Lipton, deparei-me com o seguinte fato no final de seu post no Bourne Factor : Se, para cada , existe uma relação da forma ( 2 n ) ! = M - 1 Σ k = 0 um K b c k k onde m = p o l y ( n ) , e cada um dos um K , b k e c k são p o l y ( n ) no comprimento de bits, então...
No " Conselho para um estudante de graduação iniciante ", de Manuel Blum : LEONID LEVIN acredita, enquanto faço isso, qualquer que seja a resposta para P = NP? problema, não será como você pensa que deveria ser. E ele deu alguns exemplos maravilhosos. Por um lado, ele forneceu um algoritmo de...
Dado composto peneira campo número geral é melhor conhecido algoritmo fatoração para fatoração número inteiro de . É um algoritmo aleatório e obtemos uma complexidade esperada de para fator . N O ( e √N∈NN∈NN\in\Bbb
NNNrrrf ( x + r ) = f ( x ) a < N r rf( x ) = axmodNf(x)=axmodNf(x)=a^x\;\bmod\;Nf( x + r ) = f( X )f(x+r)=f(x)f(x+r)=f(x)a <
Qual é o algoritmo mais rápido conhecido por fatorar polinômios com nnn variáveis e grau total ≤d≤d\leq d ? Aqui, nnn está crescendo ddd é fixo. A maioria dos trabalhos parece considerar o caso quando ddd está crescendo e nnn é fixo. Estou interessado em resultados tanto em campos finitos quanto...
Parece-me que a tarefa de remoção de quadrados pode ser reduzida à tarefa de fatoração , mas que não há como reduzir o fatoramento à remoção de quadrados. Existe uma maneira de tornar esse "sentimento" mais preciso, ou seja, alguma hipótese comumente considerada que seria violada se o fatoramento...