A low complexity probabilistic test for integer multiplication

DOI10.1016/J.JCO.2009.12.002MaRDI QIDQ983183zbMATH OpenOpenAlexFDO

Authors Gérald Tenenbaum, Dima Grigoriev

Publication date 3 August 2010

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2009.12.002

zbMATH Keywords

small divisorsinteger multiplicationprobabilistic test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• scientific article; zbMATH DE number 579167
• A new probabilistic primality test
• A simplified substantiation of the probabilistic Miller-Rabin primality test
• scientific article; zbMATH DE number 5845877
• Verification of the Miller-Rabin probabilistic primality test.
• A Fast Monte-Carlo Test for Primality
• scientific article; zbMATH DE number 4049704
• Information Security Practice and Experience
• Non-interactive Proofs for Integer Multiplication
• Primality testing with fewer random bits

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3635490 (Why is no real title available?)
• Designing programs that check their work
• Fast multiplication of large numbers
• Faster integer multiplication
• LOCAL DENSITIES OVER INTEGERS FREE OF LARGE PRIME FACTORS

Cited in

(1)

• Counting irreducible binomials over finite fields

This page was built for publication: A low complexity probabilistic test for integer multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q983183)