[Cryptography] rsa and semi-primes

[Thomas Kellar]

Dear Cryptography list,

I have been spending a year looking at factoring semi-primes (part of
RSA), which I suppose others have done.  I have been working with
Samuel S. Wagstaff's wonderful book _The Joy of Factoring_ which
Wright State University has been kind enough to loan me their physical
copy for over a year.   I have been avoiding complicated schemes like

https://gitlab.inria.fr/cado-nfs/cado-nfs

Because at 65 I feel too old to understand them.

I started out using Python and some C/C++ but switched to Pari-gp as
it seemed to be faster and I like it.   I have written a number of
versions of other peoples algorithms E.g., Fermat, Euler, McKee, and
etc. I put most of them on my github at

https://github.com/StartDog/semiprimefactor

I have some opinions I have arrived at on them.  Euler sucks.  Fermat
is okay.  Pollard's Rho is wonderful despite Dr. Pollard being too
busy playing his recorder at Oxford to help me with that!

I thought that I could find my own solution by investigating
semiprimes with a certain distance between the components/factors and
came up with my own factoring algorithm.  At first glance it does not
seem to be better than fermat but it does have an interesting feature.
if n is the semiprime to factor, then 2*sqrtint(n) (speaking in pari
gp terms) is about how many solutions it can find going from the
sqrtint(n) up to n searching.  With fermat you get only 1 solution.
With Euler you might not get any..  I put the program which counts the
solutions at

https://github.com/StartDog/semiprimefactor/blob/master/cntndifsol.gp

Though basically it is below:
while(1,
   r++;
   if (gcd(sqrtint(r*r + 4*n) + r,n) > 1,
      q = sqrtint(r*r + 4*n) + r;
      a = gcd(q,n);
      if (a != n,
      \\print("rndif:",r," ",q," dif-ans:",gcd(q,n));
      acnt++;
      );
      );
      if (r > n,
         print(" 2*sqrtn:",2*c);
         print("cnt solutions:",acnt);
         quit();
      );
);
r is initialized to sqrtint(n)
 An example output is below:

n1:8147 n2:9151 d:1004
n:74553197 sqrtn:8634 begin:8634 end:74553197
  2*sqrtn:17268
cnt solutions:17270

I.e., it finds 17270 solutions from sqrtint(n) up to n, n being 74553197

Now that seems to be a very high number (higher than the 1 of fermat
anyway, and higher than the 1 of a purely brute force search).

I am getting to my question. I am also preceding elsewhere in my
searching as well.  Please be kind to me I am not a professional
math person.  I was a professional programmer and have a CS degree though.

Can this be used to randomly find or help find a solution to factoring
a semi-prime?  I mean:

while(1,
   xu = random(n);
   if (gcd(sqrtint(xu*xu + 4*n) + xu,n) > 1,
      q = sqrtint(xu*xu + 4*n) + xu;
      a = gcd(q,n);
      if (a != n,
         print("xundif:",xu," ",q," dif-ans:",gcd(q,n));
         quit();
      );
   );
);

Actually finds a solution to small semi-primes fairly quickly.   I
have tried it on RSA100 and not found a solution but is this a step in
the
correct direction?  Has this already been done??   Am I repeating
someone else's mistakes?  Any pointers to something related would be
appreciated.

Thanks

Thomas