BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Ilya Volkovich (Boston College) DTSTART:20260223T210000Z DTEND:20260223T220000Z DTSTAMP:20260423T040548Z UID:NTBU/42 DESCRIPTION:Title: A Computational Perspective on Carmichael Numbers\nby Ilya Volkovich (Bo ston College) as part of Boston University Number Theory Seminar\n\nLectur e held in CDS Room 548 in Boston University.\n\nAbstract\nWe consider the problem of deterministically factoring integers provided with oracle acces s to important number-theoretic functions such as Euler's Totient function - $\\Phi(\\cdot)$ and Carmichael's Lambda function - $\\Lambda(\\cdot)$.\ nWe focus on Carmichael numbers - also known as Fermat pseudoprimes. In pa rticular\, we obtain the following results: \n\n1. Let $N$ be a `simple' C armichael number with three prime factors (also known as simple $C_3$-numb ers). Then\, given oracle access to $\\lambda(\\cdot)$\, we can completely factor $N$ in deterministic polynomial time.\n\n2. There exists a determi nistic polynomial-time algorithm that given oracle access to $\\Phi(\\cdot )$\, completely factors simple $C_3$-numbers\, satisfying some `size' boun ds. Although in this case our methods do not provide a theoretical guarant ee for all such numbers due to the required size bounds\, we show experime ntally that our algorithm can factor more than 99\\% of all simple $C_3$-n umbers up to $10^{13}$.\n\n\nOur techniques extend the work of Morain\, Re nault\, and Smith (Applicable\nAlgebra in Engineering\, Communication\, an d Computation\, 2023)\, at the core of which sits the Coppersmith's method that provides an efficient way to find bounded roots of a bivariate polyn omial over the integers. We combine these techniques with a new upper boun d on $\\gcd(N-1\, \\Phi(N))$ for $C_3$-numbers\, which could be of an inde pendent interest.\n LOCATION:https://researchseminars.org/talk/NTBU/42/ END:VEVENT END:VCALENDAR