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 <SQR(C); otherwise ENTER"
40 INPUT D: IF D <> 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