{"entities":{"Q2268250":{"pageid":2278993,"ns":120,"title":"Item:Q2268250","lastrevid":71721105,"modified":"2026-04-14T00:06:44Z","type":"item","id":"Q2268250","labels":{"en":{"language":"en","value":"Further results on implicit factoring in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5679569"}},"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":"Q2268250$D1E0790C-C4A7-4BAE-8548-76C65A0C4745","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3304a96b827f8176f9e3f64d8095ce53477e6079","datavalue":{"value":{"text":"Further results on implicit factoring in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2268250$3892EA5A-C2D5-4D41-A88A-B826B8BE959A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"254d42772e48d374436b3f07ee002a4dfe2f0276","datavalue":{"value":"1231.11141","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268250$DA7F8E79-9EAF-4FC9-9AD8-42089720A6D5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"058c2aca176150d437fa1daf515d1e072723ec31","datavalue":{"value":{"entity-type":"item","numeric-id":260043,"id":"Q260043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268250$33DAEB83-3AAD-4B00-ABCE-85ED910CBB7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c38f0b1ae0ebc51300a0596c460df119657f0d4","datavalue":{"value":{"entity-type":"item","numeric-id":276562,"id":"Q276562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268250$092C4D8C-D019-4E11-A9D8-F3EFA4A42FC3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6930ab8e1ff702d6af91a0a660c081a26e7eb4f9","datavalue":{"value":{"entity-type":"item","numeric-id":259257,"id":"Q259257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268250$70FD3F21-85F5-4F4C-8505-3ED38F0BF68B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7bab9c77774bae4661721487f1fc699428504882","datavalue":{"value":{"time":"+2010-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2268250$8E2DE42C-B1D5-4D87-9965-53DF1F530353","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"454e3d19fc47cd065747aa73b4373fc6529d8365","datavalue":{"value":"The paper extends previous results of \\textit{A. May} and \\textit{M. Ritzenhofen} [PKC 2009, Lect. Notes Comput. Sci. 5443, 1--14 (2009; Zbl 1220.11152)] about the simultaneous factoring of two RSA numbers \\(N_1=p_1q_1, N_2=p_2q_2\\), where \\(p_1,q_1,p_2,q_2\\) are primes, \\(p_1,p_2\\) and moreover \\(q_1,q_2\\) with the same bitsize and \\(p_1,p_2\\) share \\(t\\) bits. While in the paper of May and Ritzenhofen the \\(t\\) bits are the Least Significant Bits (LSBs) of \\(p_1,p_2\\) in the present paper those common bits can be the Least Significant, the Most Significant (MSBs), some portion of the LSBs and the MSBs or even to be in the middle.   It is worthwhile to point out that the \\(t\\) common bits are not known, therefore the problem differs from the problem of factoring \\(N=pq\\) assuming known some bits of \\(p\\), see \\textit{R. Rivest} and \\textit{A. Shamir} [Eurocrypt 1985, Lect. Notes Comput. Sci. 219, 31--34 (1986; Zbl 0589.94004)].   Theorem 2.1 (Section 2) gives the conditions under which \\(N_1,N_2\\) can be factored in polynomial time assuming that \\(p_1,p_2\\) share some LBSs as well as some MSBs. The used tools are lattice reduction and Gr\u00f6bner basis. Corollary 1 studies the particular case when \\(p_1,p_2\\) share only some MSBs and Corollary 2 when they share some LSBs. In this last case the paper provides (Table 1 and Figure 1) the comparison among the results of Corollary 1, the results of May and Ritzenhofen and the experimental results. Section 3 considers the case when \\(p_1,p_2\\) share \\(t\\) bits at the middle and Section 4 when also some bits of \\(q_1\\) or \\(q_2\\) are also known.   The paper includes six examples (for numbers \\(N\\) of bitsize 1000) with details of the different cases studied.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2268250$D32FA2B6-31A2-421A-AC53-19F170202CD4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268250$0385D023-DEF0-4EF1-BD9F-1A886C65E7A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268250$35C8D3F2-FDE1-47E8-BA97-248FE89364C1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c04f3816fe6022dd2c55e5dd69408ea542128be","datavalue":{"value":"5679569","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268250$B3C60A0F-240F-46E5-B0A1-6631D8CC0D0D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"306caf7867dbb78c3578a1a3bda775b521ddcdd5","datavalue":{"value":"implicit information","type":"string"},"datatype":"string"},"type":"statement","id":"Q2268250$FAFF04F4-A367-4A2F-AE89-B8A3B860C4D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e65db748320859ceaf8546ad9c9049a315c7ecb9","datavalue":{"value":"efficient factoring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2268250$754D738B-D33F-4292-8A19-3A89B6B92D61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"924c0ecace93f68fc901601a872d826f6fa35f9b","datavalue":{"value":"RSA numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2268250$434E2CEF-F7A7-4F3D-B542-EED5881F1F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff6e058e9eafa1fd442cc6638329f103ee1e3d10","datavalue":{"value":"lattice reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2268250$AE7E4FF6-A2FE-4E35-9D47-CCFB4E2FFB60","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8892955fafe16ba1bddb104e5d82ec8889d70fd9","datavalue":{"value":{"entity-type":"item","numeric-id":1313210,"id":"Q1313210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2268250$3CF20681-49EA-49AC-AFB3-511F449C7686","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":"Q2268250$596F74BC-6049-4752-A05A-010F07000431","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ab496dda92f650ba31ee891c972f2e8817b71ce","datavalue":{"value":"https://doi.org/10.3934/amc.2009.3.205","type":"string"},"datatype":"url"},"type":"statement","id":"Q2268250$6C94BBC2-9257-4EC6-BF92-F0140D484D38","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"583ce6c2d535434fce14938f6e2a272fa7c3c806","datavalue":{"value":"W2041258513","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268250$05F50687-F1BC-4097-BC70-5CF9EBA15FDA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d1e6fc88b86a40aaf01c4c267595a796b4835189","datavalue":{"value":"10.3934/AMC.2009.3.205","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2268250$FCF181B1-C9AB-4413-B0A5-2F985266F91B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5991f8fdb3d5e49c0fac8020c148042a9cf8f75f","datavalue":{"value":{"entity-type":"item","numeric-id":3562889,"id":"Q3562889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"249b208629b29ab82d68b3885f7c44970e19feaa","datavalue":{"value":{"amount":"+0.80211407","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":"Q2268250$ADBFD311-BD55-4113-91B5-685F05DAC640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aed52ef11fc7e362c22dad66667c44878775475a","datavalue":{"value":{"entity-type":"item","numeric-id":3190027,"id":"Q3190027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f89409ddfed24e7c3406b895e65ecf6c00f107d7","datavalue":{"value":{"amount":"+0.78698105","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":"Q2268250$3381B764-1D3E-43A5-B694-3A32C69B1BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e95873b2735ec8836d859797d8f1493ca056af1","datavalue":{"value":{"entity-type":"item","numeric-id":2346502,"id":"Q2346502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c09f7227a17a1c4b9ffe7302ceef84dbfe12a139","datavalue":{"value":{"amount":"+0.7769054","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":"Q2268250$7AB1146B-F8F3-408E-8910-F514545B586D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"886777faca3732034b2b577896d13110e8317162","datavalue":{"value":{"entity-type":"item","numeric-id":5300936,"id":"Q5300936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7b18140d7458aa9836c21489e035b945da0eed7","datavalue":{"value":{"amount":"+0.77400714","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":"Q2268250$7B71E26F-D377-4989-A674-F541BD38C1CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93a0bb7100e113edff6315371b6773c8e835595b","datavalue":{"value":{"entity-type":"item","numeric-id":3558305,"id":"Q3558305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abdb2887a3501cdf1f69d74e11728e68b60f7a48","datavalue":{"value":{"amount":"+0.7627029","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":"Q2268250$5ED1F60E-57FD-4284-A58C-CC26C3F9F13C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67c2888f2049e30c7a74c97c37810ff43e229cd1","datavalue":{"value":{"entity-type":"item","numeric-id":1726017,"id":"Q1726017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b1b7296dad55daa7cf5262b3b93b34ab64b966b","datavalue":{"value":{"amount":"+0.7614083","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":"Q2268250$EE172304-2ACE-4FE0-BC8C-746F46C5A38C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"136aacd4ab4d8bfc09b87913f518dcaaafaf69c4","datavalue":{"value":{"entity-type":"item","numeric-id":1647745,"id":"Q1647745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1aebe2d853e1d796840e624e945f8be23f8a9fea","datavalue":{"value":{"amount":"+0.756095","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":"Q2268250$F871E9EC-D3BC-4A1F-AA78-395BA295EA75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e38a396c450b7b3f26ce511d91754c140f4d150","datavalue":{"value":{"entity-type":"item","numeric-id":2790046,"id":"Q2790046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d462517533d17d5181512bb26d0e93b133a8732d","datavalue":{"value":{"amount":"+0.7439458","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":"Q2268250$D7D31289-C3CC-4D87-AFAE-5377C9D1026C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"baf66661e92ef6ee1d83fef428de1e5ab9a19152","datavalue":{"value":{"entity-type":"item","numeric-id":1800575,"id":"Q1800575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d3761315e19a07fa2ebdb8c647aeae1329660ba","datavalue":{"value":{"amount":"+0.7425983","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":"Q2268250$857E1D54-6A3B-40A9-A2C0-90B5A4646EEE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Further results on implicit factoring in polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Further_results_on_implicit_factoring_in_polynomial_time"}}}}}