Let N=pq be an odd semi-prime; What is the distribution of  integers that has a common divisor with N. We have shown that the distribution in [1,N-1] is a symmetric one, and there exsits a multiple of p lying to a multiple of q. We post the Maple source here.

gap := proc(a, b) return abs(a - b) - 1; end proc

HostsNdivisors := proc(N)

local i, j, g, d, L, s, t, m, p, q, P, Q, np, nq;

m := floor(1/2*N - 1/2);

L := evalf(sqrt(N));

P := Array();

Q := Array();

s := 1; t := 1;

for i from 3 to m do

   d := gcd(i, N);

    if 1 < d and d < L then P(s) := i; s++;

    elif L < d then Q(t) := i; t++; end if;

end do;

  np := s - 1;

  nq := t - 1;

 for i to np do printf("%3d,", P(i)); end do;

  printf("\n");

  for i to nq do printf("%3d,", Q(i)); end do;

  printf("\n gaps: \n");

  for i to np do

     for j to nq do

      p := P(i); q := Q(j);

      g := gap(p, q);

      printf("%4d,", g);

  end do;

    printf("\n");

end do;

end proc

HostOfpq := proc(p, q)

local alpha, s, t, g, r, S, T, i, j;

   S := 1/2*q - 1/2;

   T := 1/2*p - 1/2;

   alpha := floor(q/p);

    r := q - alpha*p;

   for s to S do

     for t to T do

       g := abs((t*alpha - s)*p + t*r) - 1;

        printf("%4d,", g);

      end do;

     printf("\n");

 end do;

end proc

MapleSource.pdf

MapleSource.mw

aRandStep2D := proc(X0, Y0, dx, dy)
  local X, Y, P, R;
  P := Array(1 .. 2);
  R := rand(1 .. 8)();
  if R = 1 then X := X0 - dx; Y := Y0 + dy; end if;
  if R = 2 then X := X0; Y := Y0 + dy; end if;
  if R = 3 then X := X0 + dx; Y := Y0 + dy; end if;
  if R = 4 then X := X0 - dx; Y := Y0; end if;
  if R = 5 then X := X0 + dx; Y := Y0; end if;
  if R = 6 then X := X0 - dx; Y := Y0 - dy; end if;
  if R = 7 then X := X0; Y := Y0 - dy; end if;
  if R = 8 then X := X0 + dx; Y := Y0 - dy; end if;
  P[1] := X; P[2] := Y;
  return P;
end proc 

SetStart := proc(b)
  local alpha, R, P;
  P := Array(1 .. 2);
  alpha := rand(1 .. b)();
  P[1] := alpha*b;
  P[2] := alpha*b;
  return P;
end proc 

RandomFactTpq := proc(N, pb, dx, dy)
  local alpha, X, Y, f, P, counter, B, n, T;
  P := Array(1 .. 2);
  counter := 0; f := 1;
  B := floor(evalf(sqrt(N))); #Set maximal searching steps
  T := floor(evalf(sqrt(N))); #For SetStart's use
  P := SetStart(T);
  X := P[1]; Y := P[2];
  while f = 1 and counter < B do  #loop
    n := pb - X - Y;
    f := gcd(N, n);
    if f > 1then break; end if;
    P := aRandStep2D(X, Y, dx, dy); #A random move
    X := P[1]; Y := P[2];
    if X < 1 or Y < 1 or N - pb - 1 < X or X <= Y then
      P := SetStart(T);       # Restart when out of borders
      X := P[1]; Y := P[2];
    end if;
    counter := counter + 1;    #Counting the searched steps
  end do;
  if  f>1  then print(Find at point (X, Y), found divisor = f, searching steps = counter);
  else print(This*time*finds*no*result, test*again!); end if;
end proc

wxbRandWalkTpqNew4.pdf