Limites mais baixos no período da fatoração inteira?

11

Nrf ( x + r ) = f ( x ) a < N r rf(x)=axmodNf(x+r)=f(x)a<Nrr

Minha pergunta agora é: Existem limites inferiores conhecidos em para aleatório ? Existe algum limite em dado que é escolhido como no RSA? Claramente, deve ser , caso contrário, pode-se avaliar em pontos sucessivos para descobrir classicamente. Seria suficiente interromper o RSA se houvesse um algoritmo de fatoração clássico que só funcione sob alguma hipótese na distribuição de , por exemplo, ou ?N R N = p q r Ω ( log ( N ) ), f ( x ) O ( log ( N ) ) r r r q ( N / log ( N ) ) R q ( rNrN=pqrΩ(log(N))f(x)O(log(N))rrrΘ(N/log(N))rΘ(N)

Uma apresentação de Carl Pomerance em " A ordem multiplicativa mod em médian " cita evidências de que é em média sobre todo , mas não tenho certeza se um algoritmo clássico que pode fatorar sob a hipótese de quebraria conclusivamente a RSA. pode ser escolhido adversamente como ou ?O ( N / log ( N ) ) N N r O ( N / log ( N ) ) N r O ( N ) ) r O ( rO(N/log(N))NNrO(N/log(N))NrO(N))rO(N)

(Nota: existe uma pergunta relacionada sobre fatoração genérica versus fatoração RSA)

Martin Schwarz
fonte

Respostas:

17

Se , o período sempre será um divisor de . Se você escolher e para prime, a menos que tenha uma sorte incrível, teremos . Eu também acredito que podemos encontrar com eficiência primos com escolhendo candidatos aleatoriamente e testando-os (isso é verdade se os eventos que er φ ( N ) = l c m ( p - 1 , q - 1 ) p - 1 = 2 p ' q - 1 = 2 q ' P ' , Q ' r p ' q 'N / 4 p p = 2 p + 1 p pN=pqrϕ(N)=lcm(p1,q1)p1=2pq1=2qp,qrpqN/4pp=2p+1ppsão primos são aproximadamente independentes; Não sei se isso foi comprovado). Assim, escolhendo cuidadosamente seus primos, o RSA ainda estará seguro contra ataques, mesmo com a hipótese adicional de fatoração fácil.

Suspeito que os números aleatórios ou aleatórios sejam extremamente improváveis ​​de terem , mas não tenho uma prova imediata disso. A hipótese é extremamente forte, e eu não ficaria surpreso se um algoritmo de fatoração eficiente já fosse conhecido para este caso.N = p q r O ( NN=pqrO(rO(N)rO(N)

Peter Shor
fonte