Don't understand way algorithm is described in paper about Monte Carlo algorithm

Question

I'm reading An Improved Monte Carlo Factorization Algorithm by Richard P. Brent. I'm not sure I'm understanding some of the notation correctly.

To my understanding $x_0$ is an arbitrary starting point and is often 2. Is this correct?

I don't understand the syntax involving repeat, for and do. For example does everything on the repeat line get done repeatedly until the until condition is met? It doesn't make sense to me repeatedly setting x to y.

Answer 1

repeat ... until forms a block -- every after the repeat is to be repeated until the condition specified by until is met. For the first repeat the last line of the block is $G = \mbox{GCD}(q,N); k = k+m$. For repeat...until everything in the block is executed at least once as the until condition is only checked when it is met.

for...do works the same way, though here if the for statement needs more than one line begin...end is being used to contain all the work that the for...do needs to do. So in your first for...do everything in on one line, but for the second there is a block of two lines following that are affected.

Keep an eye on the indentation: things indented to the same level are expected to be in the same block. So the for...do in the first place is inside the repeat...until and will be executed by the repeat until the until condition is met.

Answer 2

Please note the y is substituted f(y) on every iteration of the internal repeat .. until loop, so on each execution of x := y a different value is assigned to x.

In the language of mathematics we would say we have a sequence of some approximations or other values, and denote it with an indexed symbols like $x_i$. In the algorithm, however we do not need past values, just the most recent one. Hence we do not store all values in some indexed array, instead we just overwrite the same variable again and again with the value we currently need.

Answer 3

Attached a python realization for the proposed algorithm. The repeat was substituted by a while with the condition complemented. The N are prime numbers that should give failure as output.

from fractions import gcd

def mod(m,n):
    return m % n

def f(x,N):
    return mod(x**2+3,N)

y = 0
r = 1
q = 1
G = 0
m = 1
N = 99398833
N = 22801763489
N = 252097800623
N = 2760727302517
N = 29996224275833



while G <= 1:
    x = y

    for i in range(r):
        y = f(y,N)

    k = 0

    while  (k < r and G <= 1):
        ys = y

        for i in range(min(m,r-k)):
            y = f(y,N)
            q = mod(q*abs(x-y),N)

        G = gcd(q,N)
        k = k + m

    r = 2*r

if G == N:

    while G <= 1:
        ys = f(ys,N)
        G  = gcd(abs(x-ys),N)

if G == N:
    print("failure")
else:
    print("success")