{"entities":{"Q2898887":{"pageid":2909612,"ns":120,"title":"Item:Q2898887","lastrevid":51509387,"modified":"2026-01-18T13:49:43Z","type":"item","id":"Q2898887","labels":{"en":{"language":"en","value":"A one line factoring algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6055105"}},"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":"Q2898887$159023FA-77A4-4039-8E00-7C72613444B5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ec0db9121ff85fb5120dd67cbf3e925ced50ecef","datavalue":{"value":"1251.11088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2898887$5F8973B0-D8CF-413C-AB95-C450EE86662A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c222042a38e18aa4b545f2e91e0cf4dccce62d70","datavalue":{"value":"10.1017/S1446788712000146","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2898887$F5096CBE-E593-48D2-835F-0C3AA2B10754","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7b98fcd06345c873c02d81f93ccb99d75b18ef77","datavalue":{"value":{"entity-type":"item","numeric-id":283005,"id":"Q283005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2898887$7FC42225-717B-4FC2-8F57-54019DF4613D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8777d2a3e3d4e597d4b36b518095ec9f327c7e71","datavalue":{"value":{"entity-type":"item","numeric-id":2726645,"id":"Q2726645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2898887$07805FDC-6A04-41C1-8D28-A7D1412BED02","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fc84afb5e72a102a1e3677880bae4fbda2e5d89c","datavalue":{"value":{"time":"+2012-07-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2898887$4FE5F900-2AD4-4C06-B252-5E9FCDE367FB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2898887$8CEEB174-E351-4DCB-AA4B-7DAC0E85757A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f5492126398e1ddf0e8e00d7285568c890b3f47","datavalue":{"value":"11A51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2898887$F970480F-1446-45D6-83C5-E3FC9358DAE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2898887$B8042C97-58F3-4BE5-9DD4-8B24FEDBC580","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ff1998a344b030ee8f5b1fd90740282ecd111848","datavalue":{"value":"6055105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2898887$ABD98899-65A8-49C7-8193-94336B63D651","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96a16da0f308d1992fab2c99da58f01f7dd438e1","datavalue":{"value":"integer factorization methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q2898887$3ECC9191-701C-4FD1-8A04-7FAD5417086F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a338c89545c2e3f2511512eff4f55a1f2cae2f48","datavalue":{"value":"Lehman's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2898887$83B46F9B-D42B-435E-A3C4-D5B1110BE54A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53ee21cb567ec91ac29e1d51c8d94bc4c901fc77","datavalue":{"value":"Fermat's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2898887$8BE30518-41EB-4F41-9CB0-4D7373792E1F","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":"Q2898887$5CB22F80-44AA-43B6-9F1F-68B439DE9652","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"91ddb9c3e7753523b48c618da967b79a2c5d6510","datavalue":{"value":{"entity-type":"item","numeric-id":5429516,"id":"Q5429516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2898887$E7912196-B121-4BA6-A1EA-34828E2687A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21d566abf8ce768ffb6aacefdec9b4231f929664","datavalue":{"value":{"entity-type":"item","numeric-id":4257702,"id":"Q4257702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2898887$5BAC700E-06A4-478B-B1B3-E5F4FE859970","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"74c97b0e52a3e482e9b61cc3947f14f40a7f6d03","datavalue":{"value":{"text":"A one line factoring algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2898887$A1B8BBE8-FDFC-4C80-8462-46DD2C0AC577","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5cd363c0c8ff6939b1133580283e4e52ace70ac7","datavalue":{"value":"The paper proposes a variant of Fermat's factoring method (the original Fermat's method tries to write the number \\(n\\)\\, to factor as a difference of two squares). Although the Quadratic Sieve and the Number Field Sieve, see for instance \\textit{A. K. Lenstra} and \\textit{H. W. Lenstra} (eds.) [The development of the number field sieve. Lecture Notes in Mathematics. 1554. Berlin: Springer-Verlag (1993; Zbl 0777.00017)] are nowadays the best factoring methods, in some cases Fermat's like methods can be effective in some cases. The proposed algorithm is similar to a method due to \\textit{S. R. Lehman} [Math. Comput. 28, 637--646 (1974; Zbl 0285.10006)].NEWLINENEWLINESection 2 describes the algorithm, Section 3 proposes some tricks to speed it up and Section 4 a heuristic analysis showing that the heuristic running time of the algorithm is \\(O(n^{1/3+\\varepsilon})\\) (the same complexity of Lehman's method).NEWLINENEWLINESection 5 shows numerical results of an implementation and a comparison with the factor command in the Pari/GP package (Table 1) and Section 6 does the same (Table 2) for the Lehman's algorithm (in both cases for numbers \\(n\\) up to 40 bits. Finally Section 7 claims that the proposed method is very competitive for numbers \\(n\\) in a certain sparse class.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2898887$2A5BB473-3F1F-48BA-9146-1949AA80DDEC","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":"Q2898887$D1AB7C2E-997B-427A-894A-67FCFDF45A3B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbf37da8b0f55271d9655729b81b63501fa568c1","datavalue":{"value":{"entity-type":"item","numeric-id":4257702,"id":"Q4257702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc78de47839f38b86f2ccc03844c7d5fc0a585c7","datavalue":{"value":{"amount":"+0.8131623864173889","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2898887$E64981CC-61B2-4DCD-A3DA-2786A3122C16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce513befeb02e044605e7fc08ab4615f9eef701e","datavalue":{"value":{"entity-type":"item","numeric-id":4019632,"id":"Q4019632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc78de47839f38b86f2ccc03844c7d5fc0a585c7","datavalue":{"value":{"amount":"+0.8131623864173889","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2898887$6CBBE25F-B79D-4B85-AA3F-64AE51342A5A","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":"013ee05d02f49bbfd52fc21cf417c150896571cb","datavalue":{"value":{"amount":"+0.8006553649902344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2898887$E8EDAE0B-4AA6-4FB1-9DDF-A95344D8F52C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1b7bc7dc71d3c04b00790ea0cee4927655a9f76","datavalue":{"value":{"entity-type":"item","numeric-id":4317677,"id":"Q4317677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"013ee05d02f49bbfd52fc21cf417c150896571cb","datavalue":{"value":{"amount":"+0.8006553649902344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2898887$415BB63A-4BD6-4E01-BF7C-A53E8B6A59D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10d457553129390f33b793d5ff962b847a052587","datavalue":{"value":{"entity-type":"item","numeric-id":2796032,"id":"Q2796032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce565c071e486d2a162ae09da4f8748f72b0fabc","datavalue":{"value":{"amount":"+0.7823651432991028","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2898887$C49935D5-C3F8-45CE-9360-5F6E470E619E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2898887","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2898887"}}}}}