mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Alberico Lepore

Reply
 
Thread Tools
Old 2017-05-20, 07:48   #1
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22·127 Posts
Default 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?
Alberico Lepore is offline   Reply With Quote
Old 2017-05-20, 12:23   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-05-20, 14:02   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

19×269 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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?
Dr Sardonicus is offline   Reply With Quote
Old 2017-05-20, 14:16   #4
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22·127 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
Alberico Lepore is offline   Reply With Quote
Old 2017-05-20, 14:54   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

117678 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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...
Dr Sardonicus is offline   Reply With Quote
Old 2017-05-20, 15:48   #6
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

7748 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
Alberico Lepore is offline   Reply With Quote
Old 2017-05-20, 16:25   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-05-20, 20:53   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

19·269 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2017-05-20, 22:27   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2017-05-20, 22:39   #10
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

22×127 Posts
Default

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?
Alberico Lepore is offline   Reply With Quote
Old 2017-05-20, 23:07   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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?
CRGreathouse is offline   Reply With Quote
Reply

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 2016-09-06 15:05
Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)? Raman Factoring 1 2016-05-23 13:44
Semiprimes Hian Homework Help 15 2011-05-29 23:48
Factoring semiprimes robert44444uk Math 34 2007-07-19 17:23
time complexity of probabilistic factoring algorithms 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

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.