# What would be the scenario if P = NP for RSA algorithm?

Suppose I am using RSA for my security system. Now someone discovers find a polynomial time algorithm for RSA. Then what measure should one that such that RSA never breaks. Maybe large number of used bits or something else.

• Partial duplicate of How will security need to be changed if P=NP? – Polynomial Nov 5 '12 at 14:57
• Depends on the exact performance characteristics of that hypothetical algorithm. Polynomial can be anything from O(n) to O(n^1000). So this question is unanswerable. – CodesInChaos Nov 5 '12 at 14:59
• @Polynomial No, I don't think this question is a duplicate. It's more specific, and calls for more specific answers. – Gilles 'SO- stop being evil' Nov 5 '12 at 16:23

## 1 Answer

If it is proven that P=NP then this means that a polynomial time algorithm for breaking RSA exists. Finding that algorithm might be challenging, though. On the other hand, P could be distinct from NP and yet factoring could accept a polynomial-time algorithm. Integer factorization is not proven to be a NP-complete problem.

Moreover, "polynomial" is an asymptotic behaviour, which describes how the running time of an algorithm behaves on sufficiently large inputs. Nothing says that common RSA key sizes are "sufficiently large" for the asymptotic behaviour to be a reasonably accurate estimate of performance on these key sizes. Finally, "polynomial" does not necessarily mean "fast"; an algorithm with cost O(n12) (for a RSA modulus of n bits) would have cost 2120 for a 1024-bit RSA key, i.e. totally unachievable in practice.

That's the problem with reasoning on poorly-defined hypothetical scenarios: anything can happen, really. So the question cannot be answered, except by gut feelings. My own guts tell me that if a polynomial factorization algorithm is found, then it will probably be quite expensive for "normal" integer sizes, and use sufficiently advanced mathematics that we will have a few months or years before practical implementations appear, which should give use enough time to switch to something else (e.g. elliptic curves). But, of course, my guts are just digestive organs, good at breaking down food into nutriments; what do they really know about cryptography ?

• Bowel-based crypto needs more study. I propose a new field: Gastrocryptography – Polynomial Nov 5 '12 at 15:49
• MMM. Sounds yummy. I'll bring the S-boxes. – tylerl Nov 6 '12 at 4:27
{"ft_lang_label":"__label__en","ft_lang_prob":0.93197167,"math_prob":0.8662945,"size":2375,"snap":"2021-21-2021-25","text_gpt3_token_len":544,"char_repetition_ratio":0.10797132,"word_repetition_ratio":0.015544041,"special_character_ratio":0.23031579,"punctuation_ratio":0.119205296,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9864572,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-06-14T14:46:24Z\",\"WARC-Record-ID\":\"<urn:uuid:d445f839-662b-4165-b387-8eb00cfc272a>\",\"Content-Length\":\"169626\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:4d11718b-c5ee-4449-abdd-04b93982f02b>\",\"WARC-Concurrent-To\":\"<urn:uuid:d44e8410-52ce-4e8f-b897-adfc9bae8208>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://security.stackexchange.com/questions/23643/what-would-be-the-scenario-if-p-np-for-rsa-algorithm\",\"WARC-Payload-Digest\":\"sha1:AFJJPZNWA36KJABHDX4RR7ZVYH5NRMIE\",\"WARC-Block-Digest\":\"sha1:XE7YJ53TYHWWJZQ6KSYLSVTX3LSKN277\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-25/CC-MAIN-2021-25_segments_1623487612537.23_warc_CC-MAIN-20210614135913-20210614165913-00404.warc.gz\"}"}