Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site faron.UUCP
Path: utzoo!linus!faron!bs
From: bs@faron.UUCP (Robert D. Silverman)
Newsgroups: net.math
Subject: multiple-precision arithmetic
Message-ID: <163@faron.UUCP>
Date: Fri, 16-Nov-84 10:46:31 EST
Article-I.D.: faron.163
Posted: Fri Nov 16 10:46:31 1984
Date-Received: Sat, 17-Nov-84 01:42:16 EST
Organization: The MITRE Corp., Bedford, Ma.
Lines: 29


	I have implemented both in C and in VAX assembler a set of
multiple precision arithmetic routines which are quite fast. Using
them I have also implemented numerous state-of the art factorization
and prime testing routines including the Continued Fraction Algorithm,
Pollard P-1 and P+1, Pollard Rho, and primality testing based upon
Lucasian criteria. They are all quite fast and I believe that they
run about as fast as possible on the VAX. The continued fraction
program, for example, factors typical 40 digit numbers in about an
hour, and 50 digits numbers in about 35 hours. 
	The key problems involved in implementing multi-precision
routines on the VAX is the high cost of subroutine calls and the
relatively slow speed of the EMUL and EDIV instructions. A typical
CALLS instruction on the VAX with 3 arguments takes about 15 usec
to execute. Thus, calling a routine to (say) add 2 multi-precise numbers
is quite expensive. The EMUL instruction takes slightly less than 7 usec
to multiply 2 32 bit numbers giving a 64 bit product and EDIV takes
about 12 usec to divide a 64 bit number by a 32 bit number. One
cannot generate code to utilise EDIV and EMUL from C so the low level
arithmetic primitives must either be done in assembler, or you restrict
yourself to working in radix 2^15 so you can multiply 2 integers without
overflow.
	I would be happy to privately respond to any queries.

P.S.	I am also currently engaged in implementing the new Cohen-Lenstra
	prime testing algorithm and would like to hear from anyone who is
	interested in it.