Jump to content

A Possible Elementary Algorithm for Finding the Prime Factorization of Semiprimes


Asterisk Propernoun

Recommended Posts

((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

 

This involves the same pattern I manipulated when I tried to create a fast factorial algorithm. However, this only partially explains why this algorithm seems to work, and it's the only explanation I currently have. I'll be honest, the main reason why I think the algorithm works is because I've yet to find a counter example with pen and paper so far. The exact inner workings of the algorithm is unknown to me, but if you've came up with any proofs as to why it does or doesn't work, then please tell me.

 

My algorithm goes as so:

 

Add the semiprime by a perfect square that will give you another perfect square.

 

Find the square root of the sum.

 

Find the square root of the perfect square that you added to the semiprime.

 

Add the square root of the sum to the square root of the perfect square you added to the semiprime. This will give you the first prime number.

 

Subtract the square root of the sum by the square root of the perfect square you added to the semiprime. This will give you the second prime number.

 

The first prime number multiplied by the second prime number will give you the semiprime.

 

A working example:

 

98939209+3600=98942809

98942809^0.5=9947

3600^0.5=60

9947+60=10007

9947-60=9887

10007*9887=98939209

 

I also have some questions I would like to ask. Would there be more than one answer to the step where you add a perfect square to equal another perfect square? If you where to try using this on rsa numbers with a pre-written look up list of perfect squares, would memory be a problem? Anything you can tell me will be very helpful, thanks. :)

Link to comment
Share on other sites

Alright, since I can't edit my original post for some reason, I'll make a new one.

 

I figured out that it is possible to have at least one other solution to the step "Find a perfect square that equals another perfect square when added to the semiprime."

 

21+100=121
121^0.5=11
100^0.5=10
11+10=21
11-10=1
1*21=21

15+49=64
64^0.5=8
49^0.5=7
8+7=15
8-7=1
1*15=15

 

I figured this out by taking a second look at the pattern I made in my original post. If the semiprime is odd, then I just need to find the semiprime in the blue portion of the pattern listed here:

 

0+1=1=1^2
1+3=4=2^2
4+5=9=3^2
9+7=16=4^2
16+9=25=5^2
25+11=36=6^2
36+13=49=7^2
49+15=64=8^2
64+17=81=9^2
81+19=100=10^2
100+21=121=11^2

 

From the looks of it, I believe the second solution to the step will only result in the semiprime multiplied by one every time it's used. So perhaps one of the steps I made has to be rephrased:

 

Add the semiprime by a perfect square less than the semiprime that will give you another perfect square.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.