mersenneforum.org Semiprimes factoring. Is deterministic? What is computational complexity?
 Register FAQ Search Today's Posts Mark Forums Read

 2017-05-20, 07:48 #1 Alberico Lepore     May 2017 ITALY 22·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^2-6*y^2=(4*N)^2 x^2-3*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?
2017-05-20, 12:23   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Alberico Lepore 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^2-6*y^2=(4*N)^2 x^2-3*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?
that second equation can be changed into the form x^2-3*y^2=(2*N)^2

2017-05-20, 14:02   #3
Dr Sardonicus

Feb 2017
Nowhere

19×269 Posts

Quote:
 Originally Posted by Alberico Lepore 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^2-6*y^2=(4*N)^2 x^2-3*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?
Would you care to try this idea on N = 119?

2017-05-20, 14:16   #4
Alberico Lepore

May 2017
ITALY

22·127 Posts

Quote:
 Originally Posted by Dr Sardonicus Would you care to try this idea on N = 119?
Ops thank you so much.
For multiples of 2,3 and 7 does not work.
Other examples?

Last fiddled with by Alberico Lepore on 2017-05-20 at 14:44

2017-05-20, 14:54   #5
Dr Sardonicus

Feb 2017
Nowhere

117678 Posts

Quote:
 Originally Posted by Alberico Lepore Ops thank you so much. For multiples of 2,3 and 7 does not work. Other examples?
Yes, infinitely many in fact. I suggest you do a bit of research.

Meanwhile, I suggest this thread be moved to miscellaneous math...

2017-05-20, 15:48   #6
Alberico Lepore

May 2017
ITALY

7748 Posts

Quote:
 Originally Posted by Dr Sardonicus Yes, infinitely many in fact. I suggest you do a bit of research. Meanwhile, I suggest this thread be moved to miscellaneous math...
OK!
Thank you so much.
You have made me understand that it is not deterministic.
But what is computational complexity?
I am a passionate beginner.

2017-05-20, 16:25   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by Alberico Lepore OK! Thank you so much. You have made me understand that it is not deterministic. But what is computational complexity? I am a passionate beginner.
https://en.wikipedia.org/wiki/Comput...plexity_theory may help as may:
https://rob-bell.net/2009/06/a-begin...ig-o-notation/ admittedly I haven't read them myself and I may be confusing concepts as well

2017-05-20, 20:53   #8
Dr Sardonicus

Feb 2017
Nowhere

19·269 Posts

Quote:
 Originally Posted by Alberico Lepore 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^2-6*y^2=(4*N)^2 x^2-3*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?
If N = p * q with p and q prime, the only way I can see your approach working, is if
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 time-consuming.

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.

 2017-05-20, 22:27 #9 CRGreathouse     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.
 2017-05-20, 22:39 #10 Alberico Lepore     May 2017 ITALY 22×127 Posts ok! I can move from this equation x^2-6*y^2=(4*N^2) to this Pythagorean Diophantine x^2+9*y^2=N^2 Is this easier to solve?
2017-05-20, 23:07   #11
CRGreathouse

Aug 2006

597910 Posts

Quote:
 Originally Posted by Alberico Lepore ok! I can move from this equation x^2-6*y^2=(4*N^2) to this Pythagorean Diophantine x^2+9*y^2=N^2 Is this easier to solve?
I don't think so.

Also, it seems very common that solutions don't split N. I'm having trouble coming up with numbers, anyone want to crunch this?

 Similar Threads Thread Thread Starter Forum Replies Last Post Raman Puzzles 29 2016-09-06 15:05 Raman Factoring 1 2016-05-23 13:44 Hian Homework Help 15 2011-05-29 23:48 robert44444uk Math 34 2007-07-19 17:23 koders333 Factoring 1 2005-12-13 13:58

All times are UTC. The time now is 05:16.

Mon Nov 29 05:16:27 UTC 2021 up 128 days, 23:45, 0 users, load averages: 1.91, 1.83, 1.61

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.