[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Cryptography] rsa and semi-primes

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


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


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


Though basically it is below:
   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));
      if (r > n,
         print(" 2*sqrtn:",2*c);
         print("cnt solutions:",acnt);
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
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:

   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));

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
correct direction?  Has this already been done??   Am I repeating
someone else's mistakes?  Any pointers to something related would be


The cryptography mailing list
cryptography AT metzdowd.com