Parallel lattice basis reduction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel lattice basis reduction

Full text

Pdf (927 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Papers from the international symposium on Symbolic and algebraic computation table of contents

Berkeley, California, United States

Pages: 269 - 277

Year of Publication: 1992

ISBN:0-89791-489-9

Author

Gilles Villard

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 35, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/143242.143327 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	John Anthony Abbott, On the factorization of polynomials over algebraic fields, 1988
	2	Leonard M. Adleman, On breaking generalized knapsack public key cryptosystems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.402-412, December 1983 [doi>10.1145/800061.808771]
	3	Stephen A. Cook, The Classifikation of Problems which have Fast Parallel Algorithms, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.78-93, August 21-27, 1983
	4	M. Cosnard , B. Tourancheau , G. Villard, Gaussian elimination on message passing architecture, Proceedings of the 1st International Conference on Supercomputing, p.611-628, March 1988, Athens, Greece
	5	P. Fraigniaud. Communications intensives sur archi. tectures 5 mdmoire distribued. PhD thesis, ENS-Lyon, 1990.
	6	A.M. Frieze, R. Kannan, and J.C. Lagarias. Linear congruencial generators do not produce random sequences. In 25th IEEE Symposium on Theory of Computing, pp 4 80-4 84, 1984.
	7	J Hastad , B Helfrich , J Lagarias , C P Schnorr, Polynomial time algorithms for finding integer relations among real numbers, 3rd annual symposium on theoretical aspects of computer science on STACS 86, p.105-118, January 1986, Orsay, France
	8	J. Håstad , B. Just , J. C. Lagarias , C. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM Journal on Computing, v.18 n.5, p.859-881, Oct. 1989 [doi>10.1137/0218059]
	9	Erich Kaltofen, On the complexity of finding short vectors in integer lattices, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.236-244, March 28-30, 1983
	10	E. Kaltofen , M. S. Krishnamoorthy , B. D. Saunders, Fast parallel computation of hermite and smith forms of polynomial matrices, SIAM Journal on Algebraic and Discrete Methods, v.8 n.4, p.683-690, Oct. 1987 [doi>10.1137/0608057]
	11	R. Kannan, H.W. Lenstra, and L. Lov~sz. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers, 1984. Carnegie- Mellon University Cs-84.
	12	Ravindran Kannan , Gary Miller , Larry Rudolph, Sublinear parallel algorithm for computing the greatest common divisor of two integers, SIAM Journal on Computing, v.16 n.1, p.7-16, Feb. 1987 [doi>10.1137/0216002]
	13	D.E. Knuth. Seminurnerical algorithms. Addison- Wesley, 1981.
	14	J.C. Lagarias. The computational complexity of simultaneously diophantine approximation problems. In 23rd IEEE symposium FOCS, pp 32-39, 1983.
	15	J. C. Lagarias , A. M. Odlyzko, Solving low-density subset sum problems, Journal of the ACM (JACM), v.32 n.1, p.229-246, Jan. 1985 [doi>10.1145/2455.2461]
	16	Arjen K. Lenstra, Lattices and Factorization of Polynomials over Algebraic Number Fields, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.32-39, April 05-07, 1982
	17	Arjen K. Lenstra, Factoring polynominals over algebraic number fields, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.245-254, March 28-30, 1983
	18	A.K. Lenstra, H.W. Lenstra, and L. Lov~sz. Factoring polynomials with rational coefficients. Math. Anualen, 261 pp 513-534, 1982.
	19	H.W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8 4, pp 538-548, 1983.
	20	L. Lov~sz. An algorithmic theory of numbers, graphs and convexity. CBMS-NSF Regional Conferences Series in Applied Mathemetics, SIAM, 1986.
	21	Valtteri Niemi, A new trapdoor in knapsacks, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.405-411, February 1991, Aarhus, Denmark
	22	Abderezak Touzene , Brigitte Plateau, Optimal multinode broadcast on a mesh connected graph with reduced bufferization, Proceedings of the 2nd European conference on Distributed memory computing, p.143-152, April 1991, Munich, Germany
	23	M. Pohst, A modification of the LLL reduction algorithm, Journal of Symbolic Computation, v.4 n.1, p.123-127, August 1987 [doi>10.1016/S0747-7171(87)80061-5]
	24	S.P. Radziszowski and D.L. Kreher. Solving subset sum problems with the LLL algorithm. In Third SIAM Con.. ference on Discrete Mathematics, Clemson, SC., 1986.
	25	Y. Robert , B. Tourancheau , G. Villard, Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors, Information Processing Letters, v.31 n.1, p.21-29, April 1989 [doi>10.1016/0020-0190(89)90104-X]
	26	J.L. Roch. The PAC System and its Implementation on Distributed Architectures. In Computer with Par.. allel Architectures : T. Node, ed. D. Ga~illoud, J. Co Grossetie, Kluwer Ac. Pub., 1991.
	27	J.-L. Roch , P. Senechaud , F. Sievert-Rich , G. Villard, Computer algebra on MIMD machine, ACM SIGSAM Bulletin, v.23 n.1, p.16-32, Jan. 1989 [doi>10.1145/66062.66065]
	28	J.L. Roch, A. Vermeerbergen, and G. Villard. Loadbalancing for algebraic computations, 1992. Submitted to CONPAR92.
	29	Jean-Luis Roch , Gilles Villard, Parallel gcd and Lattice Basis Reduction, Proceedings of the Second Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.557-564, September 01-04, 1992
	30	Y. Saad, Gaussian elimination on hypercubes, Proceedings of the international workshop on Parallel algorithms & architectures, p.5-17, November 1986, Luminy, France
	31	C. P. Schnorr, A more efficient algorithm for lattice basis reduction, Journal of Algorithms, v.9 n.1, p.47-62, March 1988 [doi>10.1016/0196-6774(88)90004-1]
	32	C.P. Schnorr. Factoring integers and computing discrete logarithms via diophantine approximation. In EUROCRYPT'91, Brighton. U.K., LNCS 547, pages 281-293, 1991.
	33	Claus-Peter Schnorr , M. Euchner, Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems, Proceedings of the 8th International Symposium on Fundamentals of Computation Theory, p.68-85, September 09-13, 1991
	34	Arnold Schönhage, Factorization of Univariate Integer Polynomials by Diophantine Aproximation and an Improved Basis Reduction Algorithm, Proceedings of the 11th Colloquium on Automata, Languages and Programming, p.436-447, July 16-20, 1984
	35	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	36	D.S. Scott. Efficient all to all communication patterns in hypercube and mesh topologies. In The 6th Distributed Memory Computers Conference. Portland, Oregon USA, 1991.
	37	A. Shamir. A polynomial time algorithm for breaking the Merkle-Helhnan cryptosystem. In 23rd IEEE Symposium FOCS, 1982.
	38	Françoise Roch-Siebert , Gilles Villard, PAC: first experiments on a 128 transputers méganode, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.343-351, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120748]
	39	J. Stern. Secret linear congruencial generators are not cryptographically secure. In 28th IEEE Symposium FOCS, 1987.
	40	Jacques Stern , Philippe Toffin, Cryptanalysis of a public-key crptosystem based on approximations by rational numbers, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.313-317, February 1991, Aarhus, Denmark
	41	B. Vall~e. Une approche gdo.m~trique de la rdduction des rdseaux en petite dimension. PhD thesis, Universit6 de Caen, 1986.
	42	B. Vall~e. La r~duction des r~seaux. Autour de l'algorithme de Lenstra, Lenstra, Lov~sz. Theoretical Informatzcs and Applications, 23 3, pp 345-376, 1989.
	43	Joachim von zur Gathen, Parallel algorithms for algebraic problems, SIAM Journal on Computing, v.13 n.4, p.802-824, Nov. 1984 [doi>10.1137/0213050]