## CryptoDB

### Paper: Weak Composite Diffie-Hellman is not Weaker than Factoring

Authors: Kooshiar Azimian Javad Mohajeri Mahmoud Salmasizadeh URL: http://eprint.iacr.org/2005/111 Search ePrint Search Google In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. In the other hand factorization of the module obtained only if we can solve the Diffie-Hellman with odd-order base. In this paper we show that even if there exist a probabilistic poly-time oracle machine which solves the problem only for even-order base and abstain answering the problem for odd-order bases still a probabilistic algorithm can be constructed which factors the modulo in poly-time for more than 98% of RSA-numbers.
##### BibTeX
@misc{eprint-2005-12447,
title={Weak Composite Diffie-Hellman is not Weaker than Factoring},
booktitle={IACR Eprint archive},
keywords={public-key cryptography / Computational Complexity, Diffie-Hellman, Factoring},
url={http://eprint.iacr.org/2005/111},
note={ kushyaar@yahoo.com 12887 received 14 Apr 2005},
{"ft_lang_label":"__label__en","ft_lang_prob":0.78184485,"math_prob":0.6623689,"size":1285,"snap":"2021-31-2021-39","text_gpt3_token_len":321,"char_repetition_ratio":0.11709602,"word_repetition_ratio":0.10909091,"special_character_ratio":0.21945526,"punctuation_ratio":0.09954751,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9735462,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-23T02:04:02Z\",\"WARC-Record-ID\":\"<urn:uuid:52f94a9e-9f18-40a0-89dc-9bdf94a98970>\",\"Content-Length\":\"23154\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:48b64b22-199e-4502-a779-43c5bfdeadf9>\",\"WARC-Concurrent-To\":\"<urn:uuid:73468e3d-043b-4f02-a19a-5165ae02c922>\",\"WARC-IP-Address\":\"216.184.8.41\",\"WARC-Target-URI\":\"https://iacr.org/cryptodb/data/paper.php?pubkey=12447\",\"WARC-Payload-Digest\":\"sha1:GGBD5GHINQTQH3SF3PWHYRBYCL2UOIQ4\",\"WARC-Block-Digest\":\"sha1:W7ILCWJPISXN3JJPPV2Q2G4C6D4RTUMC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780057416.67_warc_CC-MAIN-20210923013955-20210923043955-00699.warc.gz\"}"}