Le problème de la factorisation des nombres entiers est-il plus difficile que celui de la factorisation RSA:

Ceci est un post-cross de math.stackexchange.

Soit FACT représentent le problème de factorisation d'entiers: étant donné trouver des nombres premiers et les entiers de telle sorte que $n \in \mathbb{N},$ $p_i \in \mathbb{N},$ $e_i \in \mathbb{N},$ $n = \prod_{i=0}^{k} p_{i}^{e_i}.$

Soit RSA le cas particulier du problème de factorisation où et sont des nombres premiers. En d'autres termes, étant donné que trouve les nombres premiers ou NONE s'il n'y a pas une telle factorisation. $n = pq$ $p,q$ $n$ $p,q$

De toute évidence, RSA est une instance de FACT. FACT est-il plus difficile que RSA? Étant donné un oracle qui résout RSA en temps polynomial, pourrait-il être utilisé pour résoudre FACT en temps polynomial?

(Un pointeur sur la littérature est très apprécié.)

Éditer 1: ajout de la restriction sur la puissance de calcul pour être en temps polynomial.

Edit 2: Comme l'a souligné Dan Brumleve dans sa réponse, il existe des documents plaidant pour et contre la RSA plus fort (ou plus facile que) FACT. J'ai trouvé les papiers suivants jusqu'à présent:

D. Boneh et R. Venkatesan. Rompre RSA peut être plus facile que l'affacturage. EUROCRYPT 1998. http://crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf

D. Brown: Rompre RSA peut être aussi difficile que l'affacturage. Cryptology ePrint Archive, Rapport 205/380 (2006) http://eprint.iacr.org/2005/380.pdf

G. Leander et A. Rupp. Sur l'équivalence de RSA et de factorisation en ce qui concerne les algorithmes d'anneau génériques. ASIACRYPT 2006. http://www.iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

D. Aggarwal et U. Maurer. La rupture de RSA en général est équivalente à la factorisation. EUROCRYPT 2009. http://eprint.iacr.org/2008/260.pdf

Je dois les parcourir et trouver une conclusion. Une personne au courant de ces résultats peut-elle fournir un résumé?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring Communauté
la source

Si je me souviens bien, alors le calcul de

ou la découverte de d équivaut à la factorisation, mais en tant que telle, il pourrait y avoir un moyen que RSA soit plus faible que la factorisation. En résumé, la RSA n’implique pas nécessairement la résolution du problème de la factorisation. Aucune preuve formelle connue pour leur équivalence. (

ϕ (n)

$\phi(n)$

Autant

Mohammad, pourquoi FACT n'est-il pas réductible à la RSA?

Dan Brumleve

Peut-être que je comprends mal quelque chose de fondamental. Comment montrer que l’existence d’un algorithme pour factoriser un semi-prime en temps polynomial n’implique pas l’existence d’un algorithme pour factoriser un nombre avec trois facteurs premiers en temps polynomial?

Dan Brumleve

Comment savez-vous que c'est ce que cela représente?

Dan Brumleve

S'il n'y a pas de réduction du temps multiple entre les deux problèmes énoncés, il sera difficile de montrer cela, non? Pour prouver aucune réduction poly-temps peut exister exige que nous prouvons

P \neq N P

$P\neq NP$

Fixee

Réponses:

$e$ $n=pq$ $n=pq$

$n=pq$

Dan Brumleve
la source

Merci! J'ai trouvé plusieurs autres articles avec des titres connexes, des références croisées. Je vais poster des liens ci-dessous. (Edit: les liens ci-dessous sont laids. Je n'arrive pas à mettre en forme correctement les commentaires.)

D. Boneh et R. Venkatesan. Rompre RSA peut être plus facile que l'affacturage. EUROCRYPT 1998. crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf D. Brown: Rompre la RSA peut être aussi difficile que l'affacturage. Cryptology ePrint Archive, Rapport 205/380 (2006) eprint.iacr.org/2005/380.pdf D. Aggarwal et U. Maurer. La rupture de RSA en général est équivalente à la factorisation. EUROCRYPT 2009. eprint.iacr.org/2008/260.pdf G. Leander et A. Rupp. Sur l'équivalence de RSA et de factorisation en ce qui concerne les algorithmes d'anneau génériques. ASIACRYPT 2006. iacr.org/archive/asiacrypt2006/42840239/42840239.pdf

J'ai lu les résumés et l'article d'Aggarwal et Maurer semble traiter d'un problème légèrement différent (factoriser un semi-prime par rapport au calcul de la fonction phi?). Les autres disent explicitement que le problème est ouvert. Je suppose que c'est toujours le cas sauf s'il y a un résultat plus récent que 2006?

Dan Brumleve

Il est probablement utile de mentionner que le papier de Boneh et de Venkatesan traite de la dureté de l'affacturage des semi-primes par rapport à la dureté de la rupture de la RSA. Ce que la question appelle "RSA" est en fait le problème de l'affacturage des semi-primes, ce qui peut être plus difficile que de rompre la RSA (c'est ce que suggère le journal Boneh-Venkatesan)

Sasho Nikolov

e

$e$

n

$n$

n

$n$

n

$n$

n = p q

$n=pq$

$N$ $f$ $\lfloor N^\frac{1}{f} \rfloor$ $\frac{f N^\frac{1}{f}}{\log(N)}$ $f$ $f$ $f=2$

De plus , l'algorithme de factorisation classique le plus rapide connu, appelé General Field Field Sieve , et l'algorithme de factorisation quantique à temps polynomial de Shor fonctionnent tout aussi bien pour les non-semi-premiers. En général, il semble beaucoup plus important que les facteurs de coprime que ce soit le premier.

Je pense qu'une partie de la raison en est que la version de décision de l'affacturage des co-nombres premiers est tout naturellement décrite comme un problème de promesse , et tout moyen de supprimer la promesse d'une entrée à semi-prime est soit de

introduire une indexation sur les semi-primes (ce qui en soi, je suppose, est aussi difficile que de les factoriser), ou
en généralisant le problème pour inclure les non-semi-primes.

$P\neq NP$

Enfin, il est intéressant de noter que RSA (le cryptosystème, pas le problème de factorisation que vous avez défini ci-dessus) généralise trivialement au-delà des semi-premiers.

Joe Fitzsimons
la source

P

$P$

P \neq N P

$P \neq NP$

P^{R S A} = P^{F A C T}

$P^{RSA} = P^{FACT}$

P^{R S A} = P^{F A C T}

$P^{RSA} = P^{FACT}$

P^{R S A} \neq P^{F A C T}

$P^{RSA} \neq P^{FACT}$

F A C T \in P^{R S A} ?

$FACT \in P^{RSA}?$

F A C T \in P

$FACT \in P$

F A C T \notin P

$FACT \notin P$

F A C T \in P^{R S A}

$FACT \in P^{RSA}$

Pas tout à fait une réponse complète, mais semble être une amélioration:

Les documents de recherche cités ci-dessus comparent le problème du calcul des racines éthiques mod N, c’est-à-dire l’opération de clé privée dans le cryptosystème RSA, au problème de factorisation, c’est-à-dire la recherche de la clé privée, dans les deux cas, en utilisant uniquement la clé publique. Dans ce cas, le problème de l'affacturage n'est pas le cas général, mais le cas du semi-prime. En d'autres termes, ils envisagent une question différente.

Je pense qu'il est connu, voir AoCP de Knuth, que la plupart des nombres N ont des factorisations principales dont les longueurs de bits se comparent en longueur à celle de N, en moyenne quelque chose comme 1/2, 1/4, 1/8, ..., ou peut-être même tomber plus brutalement, comme dans 2/3, 2/9, 2/27, ... mais peut-être en s’aplatissant. Ainsi, pour un nombre aléatoire général de taille suffisamment petit pour que l'on puisse s'attendre à ce que les facteurs plus petits soient détectés rapidement par la division d'essai ou l'ECM de Lenstra, alors ce qui reste peut être un semi-prime, bien que non équilibré. C'est une sorte de réduction, mais cela dépend fortement de la distribution des facteurs, et c'est une réduction lente, car elle fait appel à d'autres algorithmes de factorisation.

En outre, il n'existe aucun test connu pour déterminer si un nombre est semi-prime ou non. Cela signifie simplement que si l’on appliquait un algorithme de factorisation semi-prime à un nombre général, et qu’il échouait toujours, on résolvait un problème inconnu.

utilisateur18217
la source

L'algorithme de factorisation devrait toutefois s'exécuter en temps polynomial. Donc vous dites vraiment "si vous aviez un algorithme de factorisation multi-temps, vous auriez résolu un problème inconnu". Parce que l'on peut utiliser l'algorithme de factorisation naïf pour savoir si un nombre est un semi-prime ou non.

Elliot Gorokhovsky