{"entities":{"Q2548172":{"pageid":2558915,"ns":120,"title":"Item:Q2548172","lastrevid":48652687,"modified":"2026-01-05T12:24:55Z","type":"item","id":"Q2548172","labels":{"en":{"language":"en","value":"Fast multiplication of large numbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3354612"}},"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":"Q2548172$8B0616D8-1BCC-47A7-AE08-DCD18AA5461D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1ad1a33ad452d4280b9f33b1f1458334d06332b2","datavalue":{"value":{"text":"Fast multiplication of large numbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2548172$595A6749-5A42-4ACB-82A0-8ED253F6D05D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"db43c3bf9aa753c46d912597a93a2a4c8b7e421d","datavalue":{"value":"0223.68007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$F8F56EC1-F084-49F2-A4AE-5047CD51C62E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5cd01bcf8be4a93031b92e6e81664f5050f726fb","datavalue":{"value":"10.1007/BF02242355","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$4B3B283D-89D6-46FD-85A4-B5448EF40656","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"995198946c1a4db2a466e3988f56d70852cd6ca4","datavalue":{"value":{"entity-type":"item","numeric-id":1171379,"id":"Q1171379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2548172$6F64D52F-2A1D-4165-91B6-46BEC7C5AA9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"827cda40999de9cc474616ea9dace69944c128bd","datavalue":{"value":{"entity-type":"item","numeric-id":769164,"id":"Q769164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2548172$493345EC-AE93-46A1-9D45-906064B89A06","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2548172$419EC7D7-CE48-4F8B-91A5-BC720AD95139","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"652ad65ffdd573691be68fbfe67aa0cdf6812549","datavalue":{"value":{"time":"+1971-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2548172$AD813402-4209-4EBB-BADB-64C25ABA3C11","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b2b0e60de623df4f798a53994a9e2da04aa4ad1c","datavalue":{"value":"In dieser Arbeit werden unter der Verwendung der schnellen Fouriertransformation FFT [vgl. \\textit{J. W. Cooley} and \\textit{J. W. Tukey}, Math. Comput. 19, 297--301 (1965; Zbl 0127.09002)] zwei Algorithmen zur Multiplikation \\(N\\)-stelliger Dualzahlen gegeben, die sowohl als Turingmaschinen wie auch als logische Netze so realisiert werden k\u00f6nnen, dass ihr Aufwand durch \\(O(N\\log N (\\log \\log N)^{1+\\varepsilon})\\) bzw. \\(O(N\\log N \\log \\log N)\\) abgesch\u00e4tzt werden kann.   Beim ersten Verfahren wird die FFT wie \u00fcblich im K\u00f6rper \\(\\mathbb C\\) benutzt, beim zweiten in den Restklassenringen \\(\\mathbb Z_{F_n}\\) nach den Fermatzahlen \\(F_n=2^{2^n}+1\\). Darin ist n\u00e4mlich \\(2\\) eine \\(2^{n+1}\\)-te primitive Einheitswurzel, deren Potenzreste extrem einfache Dualdarstellungen besitzen. (German original)  English translation: In this article using the fast Fourier transform FFT [see \\textit{J. W. Cooley} and \\textit{J. W. Tukey}, Math. Comput. 19, 297--301 (1965; Zbl 0127.09002)] two algorithms for the multiplication of \\(N\\)-digit binary numbers are given that can be realized as Turing machines as well as logical nets such that their steps can be estimated by \\(O(N\\log N (\\log \\log N)^{1+\\varepsilon})\\) resp. \\(O(N\\log N \\log \\log N)\\).  In the first method FFT is used as usual in the field \\(\\mathbb C\\), whereas in the second one it is used in the residue class rings \\(\\mathbb Z_{F_n}\\) of the Fermat numbers \\(F_n=2^{2^n}+1\\). Therein \\(2\\) is a \\(2^{n+1}\\)st primitive unit root the power residues of which possess extremely simple representations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2548172$9CB3B666-336E-4BA1-97A5-4815822FABF4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$AE730EC3-CFD6-4E67-8719-584569B937D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$ADDDD764-C348-4FA6-B24E-4F3C288AB37E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd80e9ade304e6b9b43fd50d0c3436276c3c217e","datavalue":{"value":"68M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$60DE71E2-B14A-4421-9CBB-16BA0167C35B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b38169f4cef28860b2a5654a8dcaed61aeca3c61","datavalue":{"value":"65T60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$F189AC3A-8DA3-4D19-8F4B-88EDB4DA837A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ccd0b7a8494909a1824a2a8c6193e2c7c3e2ea22","datavalue":{"value":"3354612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$71F5E81B-8BF4-4223-9189-D6910B49BCF9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79f56d1bfdfb6a0fe63ee1b27574b328b70067c3","datavalue":{"value":"product of two \\(N\\)-digit binary numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2548172$A6C8B01E-F397-4A26-8507-79AF9A48B163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"949f0dd516e63c951a1a7bcd61a6b3198f3517cc","datavalue":{"value":"multitape Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q2548172$D22F43DE-1D05-45FE-AD04-CCB89EAECC0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"315f21b3246b902335a077425e7184521da12206","datavalue":{"value":"logical nets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2548172$54BECFA7-83C4-45E1-859B-DDBB675D5E60","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"dfc97f39e1c02ebcb7c1db65d6bd5f9fc24e81c6","datavalue":{"value":"Q56067772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$A7479A1B-6BCE-4410-B362-242BCE4ADB30","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":"Q2548172$885D7F20-C102-4B63-9198-48B7DE21E82B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"64178f7fb8c13a3dc9a9bcaec0ea7afe80ac68c8","datavalue":{"value":{"entity-type":"item","numeric-id":5608015,"id":"Q5608015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2548172$F37B4890-E11F-4950-85CD-04ED3E63F450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de1226518f6234cb515843a172beeb3ee5f693f0","datavalue":{"value":{"entity-type":"item","numeric-id":5582354,"id":"Q5582354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2548172$3EC8705E-1215-408B-B219-E008C346050F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd868ce1dbfc4d6f38bfad66c445685c537ca87b","datavalue":{"value":{"entity-type":"item","numeric-id":5332499,"id":"Q5332499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2548172$2D8FAFBA-D9D0-42E7-829B-853B13375BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa0540fd78fb7a7ac36ecb95287d9deaac0fb1e2","datavalue":{"value":{"entity-type":"item","numeric-id":5585021,"id":"Q5585021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2548172$CC42E8C3-FE79-49F3-ACE8-A349338C93A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de4c6eedd61c0b149650924b2d2c5ef267032b40","datavalue":{"value":{"entity-type":"item","numeric-id":2539624,"id":"Q2539624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2548172$7F7447A8-FB09-4CFF-8CE2-BF01F95E6C19","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7d7cdf118236eeb37bb5873b5df55f9ac30ff628","datavalue":{"value":"https://doi.org/10.1007/bf02242355","type":"string"},"datatype":"url"},"type":"statement","id":"Q2548172$C42A2578-31B5-4D2F-A198-6530341272D7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"803e1da263bb606e54e57580b1fe17bcff8fe2bf","datavalue":{"value":"W2083368929","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$ED7511BE-900D-472D-BAC0-DFB67F9225C2","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"69c4a27d0ea0e76f4aad63bda51e4f211efb7a67","datavalue":{"value":"journals/computing/SchonhageS71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2548172$9A924F4C-E1D2-4158-8211-86711540EA7A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e790b933822f87d9e768d320a5029e2571321f70","datavalue":{"value":{"entity-type":"item","numeric-id":3615926,"id":"Q3615926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd6b70cd9570272d9ab2b96e251d2eeae7d8a78c","datavalue":{"value":{"amount":"+0.8193010687828064","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":"Q2548172$29CBF6D3-C14F-4733-A7E5-9B55899C2457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"468e544fa5ff23a26ca568d9c251090d019d437f","datavalue":{"value":{"entity-type":"item","numeric-id":4612576,"id":"Q4612576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c8a1badc2ee154ad7f69b9ee02b608a5ba1c226","datavalue":{"value":{"amount":"+0.8153012990951538","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":"Q2548172$493DC436-B1CA-4CE8-B540-54942DDE98E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3545e94215d488953d25c9f01ea35d1701adeac8","datavalue":{"value":{"entity-type":"item","numeric-id":3325040,"id":"Q3325040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d037c9d1643c6bdbfb903ad63354f17b567da3e0","datavalue":{"value":{"amount":"+0.8147896528244019","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":"Q2548172$8EA9DEBF-0592-450A-8D03-C47A5A74EEA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d456b87d7e73274dcf821001fc28330f89e9486","datavalue":{"value":{"entity-type":"item","numeric-id":4419744,"id":"Q4419744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d7dfb91c39b7d5630e3ef69c217b71fc10adbfc","datavalue":{"value":{"amount":"+0.8098726272583008","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":"Q2548172$677B1E9D-0429-42E5-8CA2-59050F8C8B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c2f89bbc1ffaaaa2e2834a8fa553eee6db9e155","datavalue":{"value":{"entity-type":"item","numeric-id":2662018,"id":"Q2662018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae38482e57339c0aff16ea477830583d3c58d610","datavalue":{"value":{"amount":"+0.8075172305107117","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":"Q2548172$CB4EAF99-5E69-423D-B3A6-2635B45945BD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2548172","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2548172"}}}}}