Math Nerds and Computer Nerds Need to Read This

[Sigma 768]

Okay, so one day, on one of my usual Wikipedia searching sprees, I taught myself about RSA public key cryptography, and how it relied on the (assumed) hardness of prime factorization to stay secure. To be more specific, when you go through an RSA cryptosystem when you're authorized to, the system will give you a very large version of what is known as a semiprime. A semiprime is a number that has the prime factorization of only two prime numbers (for instance, 9887x10007=98939209), and, in RSA cryptography, the semiprime they use is over a hundred digits long, is composed of similar prime numbers, and would take several, in many cases thousands of years to find the prime factorization of this semiprime using brute force. Brute force, in case your wondering, is the process of systematically trialling and erring a problem using nothing but computing power. Of course, when I first learned about this, I thought to myself "Simple multiplication? That shouldn't be too hard." Well, several months have passed since then, and I've only managed to make so little progress. I'm not giving up, but at the same time, I could use some help from some of the more scholarly members of the brony community. What I'm going to do is show you what I've done so far, and see if there's anything you can add on to it. In the off chance that we actually manage to find something significant, I won't be a jerk and say it was all me. I'll be sure to credit everyone involved accordingly.

 

Oh, and as a side note, can somebody explain time complexity to me? I won't be able to 'Find the prime factorization of integers in polynomial time' if I don't even know what that means.

 

Okay, when first introduced to this problem, I first tried to brainstorm what the opposite of multiplication was. Obviously, you would say division, but that's hardly useful when you're only given the product of two numbers. After some thinking, I decided to try out square rooting:

 

98939209^0.5=9946.819039271

 

Now, I expected to get the mean (average) of the two prime numbers, but this was not the case since 9946.819039271≠9947 However, this caused me to form a kind of hypothesis. If you where to find the mean of two prime numbers, would that mean be unique to those two prime numbers alone? Of course, you could use constants or more than two prime numbers, but that's not what I asked. I asked that, lets say, we perform (5+5)/2=5, would there be any other prime numbers that you can use to replace the 5's and get the same answer? Yes.

 

(3+7)/2=5

 

Although my hypothesis was easily crushed, figuring out prime factorization by finding the mean of the two prime numbers that make up the semiprime that was given to us by the cryptographers is still very much a reality to me. If we where to find an efficient method of finding the mean of the two prime numbers using only the semiprime, then we would know that the two prime numbers where of equal distances between themselves and the mean, making the brute force method not only much faster, but much shorter since we would greatly reduce the distance between out current quantity and the two treasures that would allow us to crack RSA. I also believe that it would be possible to find the mean of the two primes and the distance between the primes and the mean without using brute force at all!

 

I digress. Basically, I'm proposing that we try to factorize the semiprime by taking the semiprime and finding the mean of the two primes instead of finding the two primes directly, and a good place to start would be what I did earlier, which is finding the square root of the semiprime. Although this will only give us the mean of the two primes if the two primes where equal to each other, the number will always fall in between the two primes. In case you're wondering; yes, I do have evidence of this:

 

((10+10)/2)^2-10x10=((20+20)/2)^2-20x20=0=0^2
((11+9)/2)^2-11x9=((21+19)/2)^2-21x19=1=1^2
((12+8)/2)^2-12x8=((22+18)/2)^2-22x18=4=2^2
((13+7)/2)^2-13x7=((23+17)/2)^2-23x17=9=3^2
((14+6)/2)^2-14x6=((24+16)/2)^2-24x16=16=4^2
((15+5)/2)^2-15x5=((25+15)/2)^2-25x15=25=5^2
((16+4)/2)^2-16x4=((26+14)/2)^2-26x14=36=6^2
((17+3)/2)^2-17x3=((27+13)/2)^2-27x13=49=7^2
((18+2)/2)^2-18x2=((28+12)/2)^2-28x12=64=8^2
((19+1)/2)^2-19x1=((29+11)/2)^2-29x11=81=9^2
((20+0)/2)^2-20x0=((30+10)/2)^2-30x10=100=10^2

 

With careful analysing, you can reach three conclusions with this data.

 

1. The size the prime numbers do not determine the distance between prime number one and prime number two multiplied together before being square rooted, and the mean of prime numbers one and two. It is the distance between the two primes that determines this.

 

2. When finding the square root of a semiprime, the result will always be greater than or equal to the lesser prime number but less than or equal to the greater prime number.

 

3. There is a detectable pattern in finding the square root of a semiprime and comparing it to the mean of it's prime factorization.

 

Keeping the list of facts in mind above, you can do some pretty impressive, yet impractical things such as the following.

 

(((p+q)/2)^2-pq)^0.5x2=|q-p|

 

but for now, let's focus on what's already on our table. I wanted to know if there was a better thing to use than ^0.5 that would take me directly to the mean of the two primes:

 

(a+b)/2=(ab)^c
Solving for c.
 
a                    b                    a+b                  a+b/2                ab                   c
0                    0                    0                    0                    0                    All Real Numbers
0                    1                    1                    0.5                  0                    No Solution
0                    2                    2                    1                    0                    No Solution
0                    3                    3                    1.5                  0                    No Solution
0                    4                    4                    2                    0                    No Solution
0                    5                    5                    2.5                  0                    No Solution
0                    6                    6                    3                    0                    No Solution
0                    7                    7                    3.5                  0                    No Solution
0                    8                    8                    4                    0                    No Solution
0                    9                    9                    4.5                  0                    No Solution
1                    0                    1                    0.5                  0                    No Solution
1                    1                    2                    1                    1                    All Real Numbers
1                    2                    3                    1.5                  2                    0.584962501
1                    3                    4                    2                    3                    0.630929754
1                    4                    5                    2.5                  4                    0.660964047
1                    5                    6                    3                    5                    0.682606194
1                    6                    7                    3.5                  6                    0.699180325
1                    7                    8                    4                    7                    0.712414374
1                    8                    9                    4.5                  8                    0.723308334
1                    9                    10                   5                    9                    0.73248676
 

I continued this pattern all the way up to (9+9)/2=9x9^0.5, and I noticed that there where two things that showed up constantly. The first was No Solution, when I tried things like (9+0)/2=9x0^c; and the second was 0.5:

 

(2+2)/2=2x2^0.5

(3+3)/2=3x3^0.5

(4+4)/2=4x4^0.5

 

and so on. This has lead me to believe that the best thing to use would be ^0.5, or square rooting to be more clear. Besides, using any other number would break the rule I've created: p≤n^0.5≤q, where p and q are the prime factors, and n is the semiprime (of course, as long as p≤q).

 

I'm afraid that this is all I have to show you at the moment. Feel free to tell me what your opinions and recommendations to this are, what you have discovered, and so on. If you want my advice, be sure to remember the first pattern list I showed you. I believe it is the most useful thing to have that's in this post if you where to try and find the mean of a semiprime's prime factorization.

Edited March 14, 2014 by Asterisk Propernoun

[Doc. Volt 2,561]

@,

 

it is 2.30 am in the morning here.. lemme grab a cofee and i will check this awesome work

[Twilight Circuits 603]

And people think I don't make sense when I talk sometimes... I have to admit I failed math so I actually couldn't follow that at all.  lol 

[Scootalove 10,689]

I never thought of this before, now my eyes are open thanks to this new discovery. To be honest, I was never good at math but I can follow this.

[Khaoios 1,970]

Holy Shit are the only two words that can come out of my mouth, .  In a good way though, b/c that is some fantastic work.  Math is not really my thing, yet computer is, so I'll be happy to check the work. 

[Doc. Volt 2,561]

@,

man.. i checked this out and this is a fucking blast, even if i studied math only to get on with engineering ( i hate thery stuff, i am a pratical man) i have to tip my hat to this, maybe you can try to create a repeating pattern with a math program, i am gonna share this with some fellas at the university more skilled than me in math

[Redneck 64]

Dude, thats some sweet hypothesis you've made there! I'm not terribly skilled with the theoretical math, more so psychics than anything else, but good luck!

[Rift enchanted 380]

....... I just skimmed it.

 

But I think a geek will do better work than a nerd will. Gosh people not using the terns correctly these days.

 

 

But anyways. Wow

[Nine 707]

If I understood that right, you're hoping to create a reliable method of finding the point equidistant from the two primes, so that a brute force attack can be optimized to begin looking within a range of numbers more likely to contain the two prime numbers that make up the semiprime.

 

A security expert I'm not, and way too much time has passed since I did anything related to cryptography to feel very brave about my answer, but if I understand RSA worth a lick, it seems to me that the square root of the semiprime is only going to give you an essentially arbitrary starting point. Using numbers as large as this encryption scheme does, the difficulty of a brute force attack is already so great that without a way of knowing with a high degree of accuracy what the midway point between the two prime numbers is, you won't be able to rule out enough ground to measurably improve your likelihood of cracking the encryption this way. You already know that you can get the same mean value from an infinite combination of numbers (you said as much yourself), so I don't see how this method will help you.

[Sigma 768]

it seems to me that the square root of the semiprime is only going to give you an essentially arbitrary starting point.

 

Assuming by arbitrary, you mean random (I never was good at my English classes), from what I can currently tell, the square root of the semiprime will always either be the same as the mean of the two primes (if the two primes where the same) or less than the mean. The size of the prime numbers alone won't determine the distance between the square root of the semiprime and the prime numbers, but is instead the distance between the prime numbers that determines this (the farther apart the primes are from each other, the farther apart their mean and the semiprime's square will be). And of course, there's still the first pattern list I presented to show that there are at least some patterns involved.

 

the difficulty of a brute force attack is already so great that without a way of knowing with a high degree of accuracy what the midway point between the two prime numbers is, you won't be able to rule out enough ground to measurably improve your likelihood of cracking the encryption this way

 

I'm not saying that we simply find the square root of the number and then brute force it from there if that's what you thought I said. I'm suggesting that we build something on top of squaring that would help us pinpoint the midway number with much better accuracy, so the time it would take to find the prime numbers would be reduced much more.

 

You already know that you can get the same mean value from an infinite combination of numbers (you said as much yourself), so I don't see how this method will help you.

 

 

without a way of knowing with a high degree of accuracy what the midway point between the two prime numbers is,

 

I don't mean to be a jerk and change the subject to dismiss you comment, but the second quote is implying that knowing the mean of the two primes would be helpful while the first one is saying that it isn't. Can you clarify this for me?

Edited March 14, 2014 by Asterisk Propernoun

[Nine 707]

I don't mean to be a jerk and change the subject to dismiss you comment, but the second quote is implying that knowing the mean of the two primes would be helpful while the first one is saying that it isn't. Can you clarify this for me?

 

The difference I intended between those two thoughts is that if you have a known mean value for X and Y, that you can still have an infinite number of solutions, but that it implies some foreknowledge of the actual values of X and Y in a given instance. Also I was thinking some other things about the incidence of prime numbers but I was having trouble phrasing myself and I omitted it .. yyyyeah

 

Alright, I'm still trying to get my head into this one because it's interesting. So let me see if I'm still following. The idea is to estimate the distance of the primes from one another based on the variance between the mean and the square root of the semiprime?

[Sigma 768]

The difference I intended between those two thoughts is that if you have a known mean value for X and Y, that you can still have an infinite number of solutions, but that it implies some foreknowledge of the actual values of X and Y in a given instance. Also I was thinking some other things about the incidence of prime numbers but I was having trouble phrasing myself and I omitted it .. yyyyeah

 

Alright, I'm still trying to get my head into this one because it's interesting. So let me see if I'm still following. The idea is to estimate the distance of the primes from one another based on the variance between the mean and the square root of the semiprime?

 

That's pretty much what I'm trying to do. I know there's an infinite number of solutions in (a+b)/2, but if you where to have a broad list of primes ready, and embrace the knowledge that the two primes will make a mean c, then you can switch the brute force method from systematically checking every prime number combination to just checking pairs that are an equal distance from c.

[Evilshy 5,090]

Can't get all mathy from work, but I can sort of explain time complexity and polynomial time. 

 

Time complexity is a way to measure how long an algorithm takes to run, in steps (i.e. calculations. 1+(5*3) takes 2 steps; 5*3, then 15+1). Specifically, a function such as n^3, where n is the length of the input string. 

Also, you generally trim out insignificantly small terms of the function. For example, if the actual function is n^3+4n, you leave out the 4n and just write n^3. This is because any inputs small enough for the 4n to be a significant number are low enough that the algorithm won't take long anyway. If you have, say, a 100 character long input, the 100^3 matters a hell of a lot more than the 4(100).

 

Polynomial time is when the upper bound of the the time (the longest it can take) T(n) is a polynomial (there aren't any n's in the exponents, only in the bases.)

 

 

 

tl;dr - time complexity is "how fast will this algorithm do it's job" and polynomial time is "reasonably fast".

 

 

I might be back later to math it up. Not sure yet.

[RrVPfX9cPtw59FpC 1,304]

Hold on...
Wait a second...

I understand...

Those are numbers.