Constructing Carmichael numbers through improved subset-product algorithms

DOI10.1090/S0025-5718-2013-02737-8MaRDI QIDQ2871190zbMATH OpenOpenAlexFDO

Authors Jon Grantham, Steven Hayman, Andrew Shallue

Publication date 22 January 2014

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.6664

zbMATH Keywords

subset sumCarmichael numbers

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Factorization; primality (11A51)

Abstract: We have constructed a Carmichael number with 10,333,229,505 prime factors, and have also constructed Carmichael numbers with k prime factors for every k between 3 and 19,565,220. These computations are the product of implementations of two new algorithms for the subset product problem that exploit the non-uniform distribution of primes p with the property that p-1 divides a highly composite Lambda.

Recommendations

• scientific article; zbMATH DE number 700553
• A new algorithm for constructing large Carmichael numbers
• On the Number of Carmichael Numbers up to x
• A New Method for Producing Large Carmichael Numbers
• The Carmichael Numbers to 10 12

Cites work

• scientific article; zbMATH DE number 3124066 (Why is no real title available?)
• scientific article; zbMATH DE number 1315279 (Why is no real title available?)
• scientific article; zbMATH DE number 700553 (Why is no real title available?)
• scientific article; zbMATH DE number 1942427 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• A computational introduction to number theory and algebra
• A new algorithm for constructing large Carmichael numbers
• An Improved Multi-set Algorithm for the Dense Subset Sum Problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Building pseudoprimes with a large number of prime factors
• Elementary cryptanalysis: a mathematical approach. Revised and updated by Todd Feil.
• Highly composite numbers. Annotated by Jean-Louis Nicolas and Guy Robin
• New generic algorithms for hard knapsacks
• STACS 2005
• The Carmichael Numbers up to 10 15
• The Pseudoprimes to 25 ⋅10 9
• The extended \(k\)-tree algorithm
• There are infinitely many Carmichael numbers

Cited in

(7)

• Carmichael numbers with a prime number of prime factors
• Primary Carmichael integers and Carmichael ideals
• Building pseudoprimes with a large number of prime factors
• Factors of Carmichael numbers and a weak k-tuples conjecture
• Advances in tabulating Carmichael numbers
• A New Method for Producing Large Carmichael Numbers
• Tabulating Carmichael numbers \(n=Pqr\) with small \(P\)

Describes a project that uses

Uses Software

• NTL

This page was built for publication: Constructing Carmichael numbers through improved subset-product algorithms

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