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

*From*: Thomas Kellar <wangude AT gmail.com>*Subject*: [Cryptography] rsa and semi-primes*Date*: Wed, 18 Nov 2020 10:48:50 -0500*List-archive*: <https://www.metzdowd.com/pipermail/cryptography>*Sender*: "cryptography" <cryptography-bounces+ben=bentasker.co.uk AT metzdowd.com>*To*: cryptography AT metzdowd.com

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 _______________________________________________ The cryptography mailing list cryptography AT metzdowd.com https://www.metzdowd.com/mailman/listinfo/cryptography

- Prev by Date:
**Re: [Cryptography] IPsec DH parameters, other flaws** - Next by Date:
**Re: [Cryptography] Possible reason why password usage rules are such a mess** - Previous by thread:
**[Cryptography] FIPS 140 validated crypto module on Android?** - Next by thread:
**[Cryptography] A bulletproof vest with moth holes** - Index(es):