GPU-NTT and Karatsuba Co-Optimization forHigh-Throughput Polynomial MultiplicationAcceleration

GPU-NTT and Karatsuba Co-Optimization forHigh-Throughput Polynomial MultiplicationAcceleration | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article GPU-NTT and Karatsuba Co-Optimization forHigh-Throughput Polynomial MultiplicationAcceleration Ruwei Huang, xiaolong Tang, Junjie Wang, Xuezheng Qin This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-8537970/v1 This work is licensed under a CC BY 4.0 License Status: Under Review Version 1 posted 13 You are reading this latest preprint version Abstract Polynomial multiplication serves as a fundamental computational primitivein modern cryptography—including fully homomorphic encryption and zero-knowledge proofs —as well as in digital signal processing. Its performanceoptimization has become increasingly critical amid the rapid development ofprivacy-preserving computation and blockchain technologies. To address the lim-itations of traditional algorithms in meeting the demands for high throughputand low latency, this study proposes a high-performance polynomial multiplica-tion accelerator based on the collaborative optimization of GPU-NTT and theKaratsuba algorithm. The method deeply integrates the asymptotically optimalcomplexity of NTT with the constant-factor efficiency of Karatsuba at moderatescales, and fully exploits the parallel computing power of GPUs to construct amodular, multi-stage pipelined acceleration framework. The divide-and-conquernature of the Karatsuba algorithm is leveraged for coarse-grained parallelism,splitting large polynomial multiplications into subproblems handled by GPUthread blocks in parallel, while each subproblem is solved with fine-grained paral-lelism using GPU-accelerated NTT kernels. An innovative zero-padding strategyis introduced to enhance the generality of the NTT kernels, and shared memorycaching is employed to alleviate GPU memory bandwidth bottlenecks. Experi-mental results on the NVIDIA RTX 4060 GPU demonstrate that the proposedmethod achieves a stable speedup of 1.43× to 1.49× over the baseline GPU-NTT for lower-dimensional polynomials, and outperforms the KNTT algorithmby up to 2.44× for higher dimensions (e.g., log2 n = 14), showing superior scal-ability and robustness. Kernel execution time analysis further confirms that themethod benefits from efficient kernel fusion and balanced workload distribution,which effectively avoids pipeline stalls and ensures high-throughput execution.This research provides a significant performance optimization solution for thepractical deployment of advanced cryptographic technologies such as FHE andZKP. Polynomial multiplication GPU acceleration Number Theoretic Transform (NTT) Karatsuba algorithm fully homomorphic encryption Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Under Review Version 1 posted Editorial decision: Revision requested 29 Jan, 2026 Reviews received at journal 29 Jan, 2026 Reviews received at journal 23 Jan, 2026 Reviews received at journal 22 Jan, 2026 Reviewers agreed at journal 18 Jan, 2026 Reviewers agreed at journal 18 Jan, 2026 Reviews received at journal 14 Jan, 2026 Reviewers agreed at journal 14 Jan, 2026 Reviewers agreed at journal 14 Jan, 2026 Reviewers invited by journal 14 Jan, 2026 Editor assigned by journal 07 Jan, 2026 Submission checks completed at journal 07 Jan, 2026 First submitted to journal 07 Jan, 2026 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-8537970","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":576344028,"identity":"293cd2b5-fc7f-46f3-8456-145a244fc2b1","order_by":0,"name":"Ruwei Huang","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAvklEQVRIiWNgGAWjYLCCxAYbCIOHBC1ppGphbDhMghbzGTmGDx7uOG+34UYC44O3bQzy5oS0yNzIMTZIPHM7eeaMBGbDuW0MhjsbCGiRkMjdJpHYdjuZXyKBTZq3jSHB4ABhLdt/JLadS2aTSGD/TayWbQyJbQfsQLYwE6eF5/1noMOSEyR7HjZLzjknYbiBoBb2tMSPP9vs7A2OJx/88KbMRp6gLTCQ2ACMHZARRKoHAnvilY6CUTAKRsGIAwCFtj2vyQHAuQAAAABJRU5ErkJggg==","orcid":"","institution":"Guangxi University","correspondingAuthor":true,"prefix":"","firstName":"Ruwei","middleName":"","lastName":"Huang","suffix":""},{"id":576344029,"identity":"822fad73-0aa7-40ac-a211-aceff58f1820","order_by":1,"name":"xiaolong Tang","email":"","orcid":"","institution":"Guangxi University","correspondingAuthor":false,"prefix":"","firstName":"xiaolong","middleName":"","lastName":"Tang","suffix":""},{"id":576344035,"identity":"5c3e5265-490d-4212-8dc0-1dfc1826518c","order_by":2,"name":"Junjie Wang","email":"","orcid":"","institution":"Guangxi University","correspondingAuthor":false,"prefix":"","firstName":"Junjie","middleName":"","lastName":"Wang","suffix":""},{"id":576344038,"identity":"a1aa3ad5-8d23-4310-a046-5785acbda498","order_by":3,"name":"Xuezheng Qin","email":"","orcid":"","institution":"Guangxi University","correspondingAuthor":false,"prefix":"","firstName":"Xuezheng","middleName":"","lastName":"Qin","suffix":""}],"badges":[],"createdAt":"2026-01-07 07:23:16","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-8537970/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-8537970/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":100542345,"identity":"39cce0ef-3d21-4bdb-8ceb-14975711715a","added_by":"auto","created_at":"2026-01-19 05:46:36","extension":"json","order_by":0,"title":"","display":"","copyAsset":false,"role":"acdc-reference","size":6449,"visible":true,"origin":"","legend":"","description":"","filename":"3549f238da194a2ca6aa5619c6ffc0c7.json","url":"https://assets-eu.researchsquare.com/files/rs-8537970/v1/43037f1521900ed4803160a6.json"},{"id":100542346,"identity":"ca892146-0f1d-4e2e-b01d-4cec86b9af6e","added_by":"auto","created_at":"2026-01-19 05:46:40","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":340729,"visible":true,"origin":"","legend":"","description":"","filename":"KaratsubaNTTSpringer.pdf","url":"https://assets-eu.researchsquare.com/files/rs-8537970/v1_covered_94bb0a5f-db67-469a-9de1-eae93b409995.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"GPU-NTT and Karatsuba Co-Optimization forHigh-Throughput Polynomial MultiplicationAcceleration","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"journal-of-king-saud-university-computer-and-information-sciences","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Journal of King Saud University Computer and Information Sciences](https://link.springer.com/journal/44443)","snPcode":"44443","submissionUrl":"https://submission.springernature.com/new-submission/44443/3","title":"Journal of King Saud University Computer and Information Sciences","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Open","inReviewEnabled":true,"inReviewRevisionsEnabled":true},"keywords":"Polynomial multiplication, GPU acceleration, Number Theoretic Transform (NTT), Karatsuba algorithm, fully homomorphic encryption","lastPublishedDoi":"10.21203/rs.3.rs-8537970/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-8537970/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"\u003cp\u003ePolynomial multiplication serves as a fundamental computational primitivein modern cryptography—including fully homomorphic encryption and zero-knowledge proofs —as well as in digital signal processing. Its performanceoptimization has become increasingly critical amid the rapid development ofprivacy-preserving computation and blockchain technologies. To address the lim-itations of traditional algorithms in meeting the demands for high throughputand low latency, this study proposes a high-performance polynomial multiplica-tion accelerator based on the collaborative optimization of GPU-NTT and theKaratsuba algorithm. The method deeply integrates the asymptotically optimalcomplexity of NTT with the constant-factor efficiency of Karatsuba at moderatescales, and fully exploits the parallel computing power of GPUs to construct amodular, multi-stage pipelined acceleration framework. The divide-and-conquernature of the Karatsuba algorithm is leveraged for coarse-grained parallelism,splitting large polynomial multiplications into subproblems handled by GPUthread blocks in parallel, while each subproblem is solved with fine-grained paral-lelism using GPU-accelerated NTT kernels. An innovative zero-padding strategyis introduced to enhance the generality of the NTT kernels, and shared memorycaching is employed to alleviate GPU memory bandwidth bottlenecks. Experi-mental results on the NVIDIA RTX 4060 GPU demonstrate that the proposedmethod achieves a stable speedup of 1.43× to 1.49× over the baseline GPU-NTT for lower-dimensional polynomials, and outperforms the KNTT algorithmby up to 2.44× for higher dimensions (e.g., log2 n = 14), showing superior scal-ability and robustness. Kernel execution time analysis further confirms that themethod benefits from efficient kernel fusion and balanced workload distribution,which effectively avoids pipeline stalls and ensures high-throughput execution.This research provides a significant performance optimization solution for thepractical deployment of advanced cryptographic technologies such as FHE andZKP.\u003c/p\u003e","manuscriptTitle":"GPU-NTT and Karatsuba Co-Optimization forHigh-Throughput Polynomial MultiplicationAcceleration","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-01-19 05:46:31","doi":"10.21203/rs.3.rs-8537970/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2026-01-29T12:45:14+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-01-29T10:46:01+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-01-23T12:00:40+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-01-22T12:20:22+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"75085056767957214667082060244917375229","date":"2026-01-18T16:24:05+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"24338257017702331667831332371043485306","date":"2026-01-18T11:02:55+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2026-01-15T03:31:19+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"128907744608566660707077780767593412833","date":"2026-01-15T01:26:43+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"277295490756681204024398933328772757076","date":"2026-01-14T20:00:45+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2026-01-14T18:13:01+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2026-01-07T11:17:49+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2026-01-07T11:16:51+00:00","index":"","fulltext":""},{"type":"submitted","content":"Journal of King Saud University Computer and Information Sciences","date":"2026-01-07T07:12:55+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"journal-of-king-saud-university-computer-and-information-sciences","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Journal of King Saud University Computer and Information Sciences](https://link.springer.com/journal/44443)","snPcode":"44443","submissionUrl":"https://submission.springernature.com/new-submission/44443/3","title":"Journal of King Saud University Computer and Information Sciences","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Open","inReviewEnabled":true,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"5b804c81-bca8-4e1b-8652-96f6005aefc6","owner":[],"postedDate":"January 19th, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"under-review","subjectAreas":[],"tags":[],"updatedAt":"2026-03-31T08:58:52+00:00","versionOfRecord":[],"versionCreatedAt":"2026-01-19 05:46:31","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-8537970","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-8537970","identity":"rs-8537970","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}