A CM-order is a reduced order equipped with an involution that mimics complex conjugation. The Witt--Picard group of such an order is a certain group of ideal classes that is closely related to the “minus part” of the class group. We present a deterministic polynomial-time algorithm for the following problem, which may be viewed as a special case of the principal ideal testing problem: given a CM-order, decide whether two given elements of its Witt--Picard group are equal. In order to prevent coefficient blow-up, the algorithm operates with lattices rather than with ideals. An important ingredient is a technique introduced by Gentry and Szydlo in a cryptographic context. Our application of it to lattices over CM-orders hinges upon a novel existence theorem for auxiliary ideals, which we deduce from a result of Konyagin and Pomerance in elementary number theory.

No abstract available.

The number field sieve is an algorithm to factor integers of the form r, 4-s for small positive r and s.This note is intended as a 'report on work in progress' on this algorithm.We informally describe the algorithm, discuss several implementation related aspects, and present some of the factorizations obtained so far.We also mention some solutions to the problems encountered when generalizing the algorithm to general integers using an idea of Buhler and Pomerance.It is not unlikely that this leads to a general purpose factoring algorithm that is asymptotically substantially faster than the fastest factoring algorithms known so far, like the multiple polynomial quadratic sieve.

Article Free Access Share on Finding irreducible polynomials over finite fields Authors: L M Adleman Dept. of Computer Science, University of Southern California Dept. of Computer Science, University of Southern CaliforniaView Profile , H W Lenstra Mathematisch Instituut, Universiteit van Amsterdam and Mathematical Sciences Research Institute Mathematisch Instituut, Universiteit van Amsterdam and Mathematical Sciences Research InstituteView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 350–355https://doi.org/10.1145/12130.12166Online:01 November 1986Publication History 51citation1,338DownloadsMetricsTotal Citations51Total Downloads1,338Last 12 Months31Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF