{"entities":{"Q1402365":{"pageid":1413105,"ns":120,"title":"Item:Q1402365","lastrevid":68845113,"modified":"2026-04-13T02:26:49Z","type":"item","id":"Q1402365","labels":{"en":{"language":"en","value":"On the security of modular exponentiation with application to the construction of pseudorandom generators"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1971853"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402365$C415991F-76B3-48D0-A23C-03C7136DEF09","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9374fdda19a4a9c47eeb5600827e24dde3427776","datavalue":{"value":{"text":"On the security of modular exponentiation with application to the construction of pseudorandom generators","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1402365$62721C8F-D6FB-46E7-A054-DB9033D44832","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"31a2a61788fb08e3e653a529f26d512b278cd97d","datavalue":{"value":"1040.94006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$97C4972D-45C2-463D-B0A9-208D1748474E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cecf1ef8f97c75d3f636331253c64cfc37610336","datavalue":{"value":{"entity-type":"item","numeric-id":178474,"id":"Q178474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402365$8035C85C-F862-4C75-B2CC-4BDE9F991069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afd104118a67d5c13a99666777bc53ce0d5bd946","datavalue":{"value":{"entity-type":"item","numeric-id":1402364,"id":"Q1402364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402365$EA59F7D9-9011-4ECD-9C45-D9BB6694A440","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"d5eab3bbb3b6673353b9ed770934b15d004ef795","datavalue":{"value":{"entity-type":"item","numeric-id":166358,"id":"Q166358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402365$FE92B950-7100-4AC6-9EAE-7F7D63B69BE2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e470d6afc31ac12c7a48dd9fcc9ab0832c78550d","datavalue":{"value":{"time":"+2003-08-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1402365$7FF428E2-166A-490D-821E-0297037EAB7F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e4b5f57e64db11cc5f47ddd6fcf184fe26bf19b","datavalue":{"value":"Let \\(N_n\\) be the set of all \\(n\\)-bit integers \\(P\\cdot Q\\), where \\(P\\) and \\(Q\\) are two odd primes of equal length. Let \\(P_n\\) be the set or pairs \\(\\langle N,g\\rangle\\) with \\(N\\in N_n\\) and \\(g\\in \\mathbb{Z}^*_N\\), the multiplicative group of naturals \\(\\leq N\\) and coprime to \\(N\\). Let \\(\\langle N,g\\rangle\\) be a uniformly distributed (u.d.) pair in \\(P_n\\), \\(R\\) u.d. in \\([0,\\text{ord}_N(g))\\) and \\(r\\) u.d. in \\(\\{0,1\\}^{\\lceil n/2\\rceil}\\). Then \\(\\text{Full}_n\\) denotes the distribution \\(\\langle N,g,g^R \\bmod N\\rangle\\) and \\(\\text{Half}_n\\) the distribution \\(\\langle N,g,g^r \\bmod N\\rangle\\).  Assuming the intractability of factoring, the authors prove that the ensembles \\(\\{\\text{Half}_n\\}_{n\\in\\mathbb N}\\) and \\(\\{\\text{Full}_n\\}_{n\\in\\mathbb N}\\) are computationally indistinguishable. They also show that this result is equivalent to the result by \\textit{J. H\u00e5stad}, \\textit{A. W. Schrift} and \\textit{A. Sharmir} [J. Comput. Syst. Sci. 47, 376--404 (1993; Zbl 0790.94013)] on the simultaneous hardness of the upper \\(\\lceil n/2\\rceil\\) bits in the exponentiation function \\(f_{N,g}(x)=g^x\\bmod N\\) (the interested reader should also consult the footnote on p.~87).  Application towards an efficient factoring-based pseudorandom generator which nearly doubles the length of its input is given. To this aim a general method on how to pick a random \\(n\\)-bit prime using only a linear number of random bits is also described.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402365$A56F1C4C-352A-4EB8-9670-558752E6DABA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ac599b3b4b403e13ff34b53d17b49cf088c1290e","datavalue":{"value":{"entity-type":"item","numeric-id":587322,"id":"Q587322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402365$0C7C4327-0FA3-4AAB-BE95-61FD10B56AE7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$904C587A-250C-4E2F-B77C-0213FCAF857B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$1D0395E3-9D0A-4CD0-BCDD-CA869E6AEFF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf81afcab7665ec308b53ada4821336ea108ff8c","datavalue":{"value":"11K45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$D0DC97D7-391B-4ABE-88E6-875975738E7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$878D469E-A44B-4791-80CB-BC734B350638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$746AC70F-EC3E-4D34-835B-ED50BDC0A3D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c38ccdf4ffb0baa319fea6438a506425be61ea29","datavalue":{"value":"1971853","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$A966D75A-A0B1-4AFA-91CA-0D05534BE4C6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8386d80d4ac63103a55c28ce581850c79d5a9342","datavalue":{"value":"modular exponentiation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402365$2DF5E3F2-3E9A-4719-9ABE-A522298FACA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e15dc5d5d8e3bb765a1ee2bbb32931074cb8b74","datavalue":{"value":"discrete logarithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402365$EFE6D733-1EF8-4054-A29E-13C90FB88194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d6fbd06d3e339fb2a2ba8506ad3e7270a982e3e","datavalue":{"value":"hard-core predicate","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402365$D2F8D085-02A1-44E4-944F-8E15A4B16E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87e089b9b1cbf11591f011701658273450c7031f","datavalue":{"value":"simultaneous security","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402365$1B7C837C-44D7-4145-B165-1671223B836A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b777100f1127212b0abed5cca160ff94fac5adf","datavalue":{"value":"pseudorandom generator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402365$D501B1F4-D8A4-45EB-B196-63A1CA2DACD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1bd60abf93f6b646eae1b74a6d813257189aa2c3","datavalue":{"value":"factoring assumption","type":"string"},"datatype":"string"},"type":"statement","id":"Q1402365$BED954F7-08A9-421F-B58B-26984390E98D","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1402365$B5F6E9C0-A5B7-4622-9490-2D52B17F2592","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5a947411c1f54f83f8b62d440027eb910dd4b55c","datavalue":{"value":"https://doi.org/10.1007/s00145-002-0038-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1402365$1157D285-5BB0-4A42-AE9A-4DA28827F3BC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"17e62c279e0cce813b48c295c57548debb11b3cd","datavalue":{"value":"W1979828147","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$ECF5B2B0-1407-459D-87E4-3A433CF77BA3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f59a36ab91a06215f7cfbd5fc4edaa496b2e5f78","datavalue":{"value":"10.1007/S00145-002-0038-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1402365$688A0E25-F55A-47A8-B7DC-CA7AE4DC4E28","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54509129d4ce84027f502fcd59f18c5298fba561","datavalue":{"value":{"entity-type":"item","numeric-id":3191966,"id":"Q3191966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a62b4f9fcca5d9a2bdc16672c8bded28afe20a9","datavalue":{"value":{"amount":"+0.8340504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$B2CE1E99-D954-4D87-BE32-BBC419A00406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56338ce843ab5a3ce9a625d1392e931400fcd57b","datavalue":{"value":{"entity-type":"item","numeric-id":4536819,"id":"Q4536819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0443477dbbc33f1084954f73341b4d909ed4ed4","datavalue":{"value":{"amount":"+0.81816846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$0A6A8024-0CA2-4E19-96EB-1D45B4E7C7AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cd7aaf7c34258505e05c8853349d1bf8297924c","datavalue":{"value":{"entity-type":"item","numeric-id":814844,"id":"Q814844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b2ed5740122683f1d98b8676f1065a612d7d1b1","datavalue":{"value":{"amount":"+0.8036721","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$9DB9F89B-277C-4032-ACCF-1D80E83B80E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32d5b781f047a783661d256425d5a79685f5a5e8","datavalue":{"value":{"entity-type":"item","numeric-id":4249340,"id":"Q4249340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8d06a100e1fc4d4a7579cc835ea2c7a46bd7f87","datavalue":{"value":{"amount":"+0.7985895","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$41E6E0C2-3A00-4121-A80B-B82312A18430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbfe3b5191728452d4088251a3221611a8805cba","datavalue":{"value":{"entity-type":"item","numeric-id":3702366,"id":"Q3702366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2c5313049b624561180514a9d576a84aaee3e06","datavalue":{"value":{"amount":"+0.79288524","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$4304A943-6953-4139-BC16-8488B64EDFA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9feff64987499dffbd074628f08d029e252f4b9","datavalue":{"value":{"entity-type":"item","numeric-id":1317484,"id":"Q1317484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5a1b121b68bff0b59a0551f3b4fffe030a47d8d","datavalue":{"value":{"amount":"+0.7853522","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$F2202E59-E854-42FC-A171-E55B9A27DE8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f346e0ef96641380ded90a4e124cd47d9798627","datavalue":{"value":{"entity-type":"item","numeric-id":3787913,"id":"Q3787913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cd71e159a51a2c63a6990fe028467c47f0ef9c7","datavalue":{"value":{"amount":"+0.78033054","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$B205E1DC-F83E-49CB-8790-B6F4C5894A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fb5012d2e441133780e876de94ae3853d3fd44d","datavalue":{"value":{"entity-type":"item","numeric-id":912919,"id":"Q912919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c996a5de291c8b2ba89b6ba56d111d11623a349","datavalue":{"value":{"amount":"+0.77910167","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$311D291A-DC15-43F1-B8D3-E0E027808983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77650e8dc63e1c3b6a99f45b2d3fe78493664371","datavalue":{"value":{"entity-type":"item","numeric-id":4414270,"id":"Q4414270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e9c06b55fcdd88418772fd902f69f1f43f30665","datavalue":{"value":{"amount":"+0.77146626","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$927A1DC2-7D51-4FC0-A99F-C04616780AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c318de8931392827d9802689578010469ed4e4a7","datavalue":{"value":{"entity-type":"item","numeric-id":3149873,"id":"Q3149873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15f6664c6cd4e37dcb64315a95f3fb54b4d339d5","datavalue":{"value":{"amount":"+0.7667221","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1402365$FAE4439D-B47C-4C6B-AA0C-8BC9F6401C64","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the security of modular exponentiation with application to the construction of pseudorandom generators","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_security_of_modular_exponentiation_with_application_to_the_construction_of_pseudorandom_generators"}}}}}