20170520, 07:48  #1 
May 2017
ITALY
2^{2}·127 Posts 
Semiprimes factoring. Is deterministic? What is computational complexity?
I'm a beginner enthusiast of cryptography.
I found a bug in the RSA algorithm Both N is the semiprimes number to be factorized Then just find the fundamental solutions of one of the two generalized Pell equations x^26*y^2=(4*N)^2 x^23*y^2=4*N^2 And make MCD (Maximum common divisor) with N The questions I am sending to you are: Is deterministic? What is computational complexity? 
20170520, 12:23  #2  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:


20170520, 14:02  #3  
Feb 2017
Nowhere
19×269 Posts 
Quote:


20170520, 14:16  #4 
May 2017
ITALY
2^{2}·127 Posts 
Ops thank you so much.
For multiples of 2,3 and 7 does not work. Other examples? Last fiddled with by Alberico Lepore on 20170520 at 14:44 
20170520, 14:54  #5 
Feb 2017
Nowhere
11767_{8} Posts 

20170520, 15:48  #6  
May 2017
ITALY
774_{8} Posts 
Quote:
Thank you so much. You have made me understand that it is not deterministic. But what is computational complexity? I am a passionate beginner. 

20170520, 16:25  #7  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
https://robbell.net/2009/06/abegin...igonotation/ admittedly I haven't read them myself and I may be confusing concepts as well 

20170520, 20:53  #8  
Feb 2017
Nowhere
19·269 Posts 
Quote:
at least one of x^2  6*y^2 = k x^2  2*y^2 = k is solvable with k = p, p, q, or q. Even if this is true, finding the solutions might be inordinately timeconsuming. You might look up known methods of factoring using continued fractions; however, these only work in a reasonable amount of time with numbers of around 50 decimal digits IIRC. 

20170520, 22:27  #9 
Aug 2006
3·1,993 Posts 
Solving Pell equations is not easy. Lenstra has a L(1/2) method, but NFS is L(1/3). So even if this works I don't think it's an improvement.

20170520, 22:39  #10 
May 2017
ITALY
2^{2}×127 Posts 
ok! I can move from this equation
x^26*y^2=(4*N^2) to this Pythagorean Diophantine x^2+9*y^2=N^2 Is this easier to solve? 
20170520, 23:07  #11  
Aug 2006
5979_{10} Posts 
Quote:
Also, it seems very common that solutions don't split N. I'm having trouble coming up with numbers, anyone want to crunch this? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
What is the fastest algorithm and its computational complexity to the subset(bit) AND problem?  Raman  Puzzles  29  20160906 15:05 
Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)?  Raman  Factoring  1  20160523 13:44 
Semiprimes  Hian  Homework Help  15  20110529 23:48 
Factoring semiprimes  robert44444uk  Math  34  20070719 17:23 
time complexity of probabilistic factoring algorithms  koders333  Factoring  1  20051213 13:58 