'Subject: Pollard's Rho factorization method, Brent's modification.
'Author : Sjoerd.J.Schaper
'Date   : 21-12-2003
'Code   : QuickBasic, PDS, VBdos
REM $LANG: "qb"
REM $INCLUDE: 'largeint.bi'
DEFLNG I-M, R
DECLARE SUB Prntfr (fr&)
'Print current factor.
CONST N = 0, d = 1, p = 2
CONST x = 3, y = 4, ys = 5
b = LargeInit(ys, "pollarho")
CLS : tim# = TIMER: lin = 8

begin:
LOCATE 1, 1
PRINT "   +-----------------------------+"
PRINT "   |  input number N to split,   |"
PRINT "   |  and iteration constant c,  |"
PRINT "   |  0 to exit.                 |"
PRINT "   |                             |"
PRINT "   +-----------------------------+"
LOCATE 5, 7: INPUT ; "N"; Ni$
IF INSTR(Ni$, "'") THEN GOTO begin
IF VAL(Ni$) < 2 THEN GOTO eind
INPUT ; " c"; b$: b = 0 '              f(y) = y^2 (mod N) + b
IF ABS(VAL(b$)) < MB \ 2 THEN b = ABS(VAL(b$))
IF b = 0 THEN b = 3 '                  default b
m = INT(LEN(Ni$) * 2.3026) '           m = presumed length of
'                                      the non-periodic segment
CLS : LOCATE 8, 1
Readst N, Ni$
Printn N, "  N = ", "", 2

sw = 0: c = 0
IF IsPPrm(N, d, 5) THEN '              preliminary tests
   Prints " N is probably prime", 2
   GOTO begin
ELSE
   Swp p, d: Gcd N, p, d
   IF NOT Isf(d, 1) THEN GOTO jump
   IF IsSqr(N, d) THEN GOTO jump
END IF

Prints "  m =" + STR$(m) + "  c =" + STR$(b), 0
Letf y, 0: Letf p, 1: r = 1
DO
   Dup y, x
   FOR i = 1 TO r
      Modsqu y, N: Inc y, b '          y:= f(y)
   NEXT i
   c = c + r: k = 0
   DO
      Dup y, ys
      il = r - k
      IF m < il THEN il = m '          il:= min(m, r - k)
      FOR i = 1 TO il
         Modsqu y, N: Inc y, b '       y:= f(y)
         Dup x, d: Subt d, y
         Sets d, 1: Modmlt p, d, N '   p:= p * abs(x - y) mod N
      NEXT i
      c = c + 2 * il: Prntfr (c)
      IF Isf(p, 0) THEN sw = -1: GOTO jump
      Gcd p, N, d: k = k + m
      s = NOT Isf(d, 1) '              gcd(p, N) > 1 ?
   LOOP UNTIL k >= r OR s
   r = 2 * r
LOOP UNTIL s

jump:
IF sw THEN '                           case p = 0, backtrack cycle
   DO
      Modsqu ys, N: Inc ys, b '        y:= f(y)
      Dup x, p: Subt p, ys
      Sets p, 1: c = c + 1
      IF Isf(p, 0) THEN Letf p, 1
      Gcd p, N, d
   LOOP WHILE Isf(d, 1) '              gcd(abs(x - ys), N) > 1
END IF

IF c > 0 THEN
   Prints "  t =" + STR$(c), 1 '       number of multiplications (mod N)
END IF
Divd N, d, p '                         gcd in d
IF Isf(d, 1) OR Isf(p, 1) THEN
   Prints "failure", 1
ELSE
   Printn d, "  f = ", "", 1
   Printn p, "N/f = ", "", 2
END IF
Prints "", 1
lin = CSRLIN: GOTO begin

eind:
LOCATE lin, 1
g$ = STR$(CSNG(TIMER - tim#))
Prints "Timer:" + g$ + " s", 1
CALL Term
SYSTEM

SUB Prntfr (fr&)
STATIC Ton AS SINGLE
   IF TIMER - Ton > 1 THEN
      lin = CSRLIN: Ton = TIMER
      PRINT "  fr ="; fr&; SPC(6);
      LOCATE lin, 1
   END IF
END SUB

