From msuinfo!agate!howland.reston.ans.net!usc!elroy.jpl.nasa.gov!swrinde!news.dell.com!natinst.com!hopper.acm.org!ACM.ORG!WARLOCK Sun Sep 5 14:33:31 1993 Path: msuinfo!agate!howland.reston.ans.net!usc!elroy.jpl.nasa.gov!swrinde!news.dell.com!natinst.com!hopper.acm.org!ACM.ORG!WARLOCK From: warlock@ACM.ORG Newsgroups: sci.crypt Subject: Seek Integer Factoring Program Date: 2 Sep 1993 16:43:48 GMT Organization: ACM Network Services Lines: 59 Message-ID: <2657s4$92b@hopper.acm.org> Reply-To: warlock@ACM.ORG NNTP-Posting-Host: acm.org vpcsc4@sfsuvax1.sfsu.edu (Emmet McLean) asks: >can anyone recommend a shareware program which factors long >integers (not multiple precision integers)? I am rewriting a paper entitled "Riddling the RSA Sphinx" which was *lost* for almost three years in the editorial maze of CRYP- TOLOGIA in spite of several *status inquiries*. When finally apprised of this unfortunate impasse, I withdrew the paper. It contains several concise "tight loop" factoring algorithms using only addition, subtraction, and shifting operations to avoid otherwise compute-intensive functions such as taking of roots, testing for squareness, computing residues or maintaining large tables of primes, etc. -- characteristics typical of most factor ing algorithms. (The only division or multiplication operations permitted are those involving powers of 2 which can be accom plished by appropriate high-speed register shifting). These algorithms are also designed for even faster operation in parallel environments where solution spaces may be allocated to multiple processors. For example, Step 30 of the BASIC algo rithm given below for factoring the composite C allows the search for prime p to begin at any selected value less than SQR(C) for each processor. This algorithm is a "rethink" in the terms out lined above of the first formal factoring algorithm devised by Fermat who sought to express C as the difference of two squares. Algorithms such as the one below can serve also as subfunctions of "larger" algorithms such as the Morrison-Brillhart algorithm which require factoring smaller composites in order to factor the larger target composite. In essence, the algorithm below seeks to express C = p*q as the arithmetic sum of a series of consecutive odd numbers beginning with low odd integer L and ending with high odd integer H with variable S representing their running sum. When a series is found where S = C, p and q can be immediately derived by the method of Fermat. As can be seen, the "tight loop" portion of this algorithm consists of steps 130 and 140 which are executed until C is factored or found to be prime. 10 PRINT "Input Modulus C:": INPUT C 20 R = FIX(SQR(C)): IF C = R^2 THEN PRINT "C ="R"SQUARE": END 30 PRINT "Input starting p search value 0 GOTO 70 50 H = (2*R)-1: IF C MOD 4 = 1 THEN L = 5 ELSE L = 3 60 GOTO 100 70 H = D+(FIX(C/D))-1: IF H MOD 2 = 0 THEN H = H-1 80 L = FIX(C/D))-D+1: IF L MOD 2 = 0 THEN L = L-1 90 IF L MOD 4 <> C MOD 4 THEN L = L-2 100 IF H MOD 4 <> C MOD 4 THEN H = H-2 110 PRINT "H ="H, "L ="L, "R ="R, "D ="D 120 S = ((H+L)/2)*((2+H-L)/2) 130 I = I+1: IF S > C THEN S = S-(2*L+2): L = L+4: GOTO 130 140 IF S < C THEN H = H+4: S = S+(2*H-2): GOTO 130 150 IF (2+H-L)/2 = 1 THEN PRINT "Modulus "C" is prime.": END 160 PRINT "Modulus "C" ="(2+H-l)/2"*"(H+L)/2" in "I-1" iterations.": END WARLOCK