{"entities":{"Q647854":{"pageid":649703,"ns":120,"title":"Item:Q647854","lastrevid":42623211,"modified":"2025-07-07T07:54:43Z","type":"item","id":"Q647854","labels":{"en":{"language":"en","value":"One approach to factorization of positive integers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5975527"}},"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":"Q647854$DBD60E5F-2174-4887-997A-82E51C3D3C8A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3ad4dd1609b1554c4ff25e7b1a4cf230e68f786b","datavalue":{"value":{"text":"One approach to factorization of positive integers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q647854$E35E4F1E-1C9A-4104-A9E0-F89FA9D9A2FE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"272dd66afa026edd6528e33af68492c6de131f11","datavalue":{"value":"1254.11115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q647854$16729905-126E-4961-A98A-2E2C7A77E656","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"36a8bd8059a7e2e6447ab54925adbe5aa10d2ad3","datavalue":{"value":"10.3103/S1066369X11040037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q647854$ED8001E2-434D-4250-9968-9D24215A566C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9a274f43c153fe0b8c0962b1d1a287a46f2839b","datavalue":{"value":{"entity-type":"item","numeric-id":647852,"id":"Q647852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q647854$64DF33D8-5B31-44B4-A350-BA7809531CB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"193f426dc3bf45c622623f937286f38c3d3fef0d","datavalue":{"value":{"entity-type":"item","numeric-id":647853,"id":"Q647853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q647854$9908F793-C81D-4D66-A4AF-FF343855828C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e521a8b65f31ddf1284b736fa615d9780f147ac3","datavalue":{"value":{"entity-type":"item","numeric-id":465141,"id":"Q465141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q647854$CCE33E15-6A00-4F54-A478-080E0747DFB9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62318960435ff4e0b6f0bda102e1b989b0fc569e","datavalue":{"value":{"entity-type":"item","numeric-id":268929,"id":"Q268929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q647854$C679E259-D548-4AC7-9704-D6A7CAB87E23","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4d73454e0170207192c80832266863a4752e4daa","datavalue":{"value":{"time":"+2011-11-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q647854$666597AB-0343-4372-B81F-915A3A5A6258","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b78e11b18c59f474a4cf4340e440ea17462fd302","datavalue":{"value":"This paper proposes a new variant of the Number Field Sieve (NFS). The Quadratic Sieve (QS) and NFS are the better known methods for factoring large integers \\(N\\),\\, and many improvements and variants have been proposed.  The NFS method see [\\textit{A. K. Lenstra} and \\textit{H. W. Lenstra}, The development of the number field sieve. Lecture Notes in Mathematics. 1554. Berlin: Springer-Verlag (1993; Zbl 0777.00017)] chooses an irreducible polynomial \\(P(x)\\)\\, of small degree \\(r\\)\\, (usually \\(r=4,5,6\\)), an integer \\(m\\)\\, such that \\(P(m)=N\\)\\, and a root \\(\\alpha\\)\\, of \\(P(x)\\)\\, and try to factor expressions \\(a+bm\\)\\, and \\(a+b\\alpha\\)\\, over a factor base of rational integers and a factor base of prime ideals of \\(Q(\\alpha)\\). The proposed method does not require the use of the second base and consider only numbers \\(a+bm\\)\\, such that \\(a+bx\\)\\, is a quadratic residue modulo \\(P(x)\\).  Section 1 summarizes the NFS method and Sections 2 and 3 describe the proposed new technique for \\(r=2\\)\\, (and \\(N=pq\\),\\, a RSA number) and give a toy example (\\(N=4897\\)). Finally Section 4 discusses the complexity of the method concluding that is the same as the complexity of the QS method.  The Conclusion Section summarizes the main advantages of the proposed method but the authors point out that ``in practice one cannot use the irreducible polynomial of the degree \\(r=2\\)\\, for factoring extremely large numbers; in solving this problem the NFS method is most efficient.''","type":"string"},"datatype":"string"},"type":"statement","id":"Q647854$11C169F5-7AE3-4F1C-B989-63CD7FAB39BA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q647854$CF661553-28FC-4398-BB59-B5C1BC322C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q647854$1BD53CCC-391F-49A8-9D05-6356C95E234E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q647854$D9CB21EB-41C5-4007-BEB1-F7BD84BD5DF8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6cb5b953a966ce4bfa8962a98d760a4db9febf45","datavalue":{"value":"5975527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q647854$51AB94EA-B3C3-4C34-8BE7-9D2D421E0544","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7eefc55d19757133a6d7014afa3f41525412be29","datavalue":{"value":"factoring","type":"string"},"datatype":"string"},"type":"statement","id":"Q647854$AA0C3F95-E5DE-48E2-A36C-7EAADBCF06C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a82b8e03ae823b77de3f4c98319324232e2a2036","datavalue":{"value":"quadratic sieve","type":"string"},"datatype":"string"},"type":"statement","id":"Q647854$46DDC63D-4C37-49C4-A776-7744CCBDD61A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d92933569277d10edac01435fc2574cbf9ecacc","datavalue":{"value":"number field sieve","type":"string"},"datatype":"string"},"type":"statement","id":"Q647854$470118B1-8F8A-4F19-8D96-CE5A784D2E2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d324115690d97a4f2702714fef4213f7d99fe719","datavalue":{"value":"RSA","type":"string"},"datatype":"string"},"type":"statement","id":"Q647854$EBFC953D-36DF-462D-BB37-3E2665D35C3A","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":"Q647854$87EF5042-D9BC-4B9C-9058-CA438056A510","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":"Q647854$B369A678-B8CE-4DCB-998F-E0225C19E2C9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb2c469b81d6110dea3018c85fde542bb3eec30b","datavalue":{"value":{"entity-type":"item","numeric-id":689067,"id":"Q689067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q647854$C7F21CE7-6CAE-4857-A7B2-A5D8EA4D16F4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba4388bc86b01001607c8516f70b76d9a01f5859","datavalue":{"value":{"entity-type":"item","numeric-id":4036860,"id":"Q4036860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffcd318aee59f7bf9e5ffc0b6f1d2442f9d8c269","datavalue":{"value":{"amount":"+0.85848457","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":"Q647854$96FF8542-C845-4CD5-B1B8-58D8B0D4DD9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6854740df62f7181621220b109001298405f7f70","datavalue":{"value":{"entity-type":"item","numeric-id":3117605,"id":"Q3117605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"644516d16c79729727839e80e993fdec50a3cba5","datavalue":{"value":{"amount":"+0.84339166","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":"Q647854$D510381E-B83D-4973-BEB9-7CAB25C7D0D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"647362e651e855641676757bb17ce8bb5eda24d8","datavalue":{"value":{"entity-type":"item","numeric-id":4273679,"id":"Q4273679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05d51dac5cb6422370fb49bfb2a7aa317154b8c9","datavalue":{"value":{"amount":"+0.8220167","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":"Q647854$7FC0D22F-C7B2-497B-82AB-11EEB3CC8194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a03881068bedd0c1ad8cb6a0e303bdcb7e67d0ad","datavalue":{"value":{"entity-type":"item","numeric-id":3166983,"id":"Q3166983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9aef7ec25bbfda30483859186481eb4a2a503621","datavalue":{"value":{"amount":"+0.815037","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":"Q647854$CAC4378E-DD65-47B1-A802-F0907D0D1295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9316cdecc5a0b7aa562b0d099df537dc56485f33","datavalue":{"value":{"entity-type":"item","numeric-id":3838139,"id":"Q3838139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2cdd6410809f1c419056718c700bfd3351c8177","datavalue":{"value":{"amount":"+0.80982506","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":"Q647854$230DA4B0-9438-49E7-A396-0A8C47CF3CC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15fa2bda4f638e61c1faba5506895bbdb8899faf","datavalue":{"value":{"entity-type":"item","numeric-id":4343449,"id":"Q4343449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47a101fcdae90d3bdc0a930c2f4a4be6d93c920c","datavalue":{"value":{"amount":"+0.7973964","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":"Q647854$7E2914D4-F318-407A-9C3C-53A5A6231DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4c2b51559e08fb5d7c7dfc0c1c566658dff7804","datavalue":{"value":{"entity-type":"item","numeric-id":4273681,"id":"Q4273681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b7e2fc39bef377ef1304adecfecbf06fbda514e","datavalue":{"value":{"amount":"+0.7942516","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":"Q647854$AC2C957A-ED88-478A-96D7-3F44E48ABA48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d06431d867fa62cd3619bcfdb99fcd2b8fd8cfe","datavalue":{"value":{"entity-type":"item","numeric-id":2898887,"id":"Q2898887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c84f5723f9305833b4b09285d5f8c5e5047c6cd","datavalue":{"value":{"amount":"+0.7931905","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":"Q647854$F023B789-E105-416F-BEF7-C747DA594714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d9572ef655f9045435492a520104fe1af8a9337","datavalue":{"value":{"entity-type":"item","numeric-id":4648972,"id":"Q4648972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8e3bc2a41b9a0bf689c59ef2679f7555182f52e","datavalue":{"value":{"amount":"+0.7922932","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":"Q647854$AB767FDB-A53E-461C-BFAC-95C8F1770C37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85663eca8f471f07f7e57a032468f6f86da4a127","datavalue":{"value":{"entity-type":"item","numeric-id":1310453,"id":"Q1310453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"638f3c93f873c20d9bc6c02c8223cc43c9d6297e","datavalue":{"value":{"amount":"+0.7901499","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":"Q647854$DF2EF743-F61E-4556-8979-5B43B97BE18C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:647854","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:647854"}}}}}