Calling all Maths geniuses - help is requested !

An interesting point to notice though...

Let's not care (yet) about how to do that though. Everytime you reach one of your solutions (i.e. finding a and b so that for the 2 integer values of x the equation = 0), we can notice that the two roots (x1 and x2) multplied give b.

Similarly, we can notice that a is x1+x2...

Examples with your examples:
- a=225, b=3150 gives x1=15 and x2=210. x1*x2 = 15*210 = 3150, x1+x2 = 225
- starting with 23 and 1866, we have a=167 and b=1860, x1=12 and x2=155, and 12*155=1860 and 12+155 = 167

It seems to work everytime.

Thus the problem can be reduced into finding the closest number lower than the starting b that can be composed in the form of a product.

So...
- We look for b, by decreasing the starting b (b0) of 1 unit everytime.
- For each new b, find the highest divider d (there are many algorithms for that)
- b/d gives x1
- a = x1+d
- we can remark that d = x2 everytime as well...
- test that x1²-ax1+b = 0 (can be evaluated quickly too)
- if no, discard and go on searching for the next d.
- until d

Originally posted by tauristercus

I've had a very long interest (obsession ?) with prime numbers, especially with recovering the initial 2 prime numbers that were multiplied together to give a product. e.g 7 x 11 = 77.
In other words, if you were only given the product 77 and were asked to determine the original 2 primes used to create this value, you'd basically have little choice except to use "brute force" techniques and hammer away at this 77 value with every prime number that was smaller than the square root of this value ... eventually finding that 7 is one prime factor and therefore 11 is the other prime factor.

It's taken me a number of years but I've successfully derived an alternative method of retrieving the prime factors of ANY product that is supplied. It's already been succesfully tested on small digit length products and succesfully extracts both primes in each case. The only remaining issue I have is the subject of this thread, and if it can be resolved, will make this an incredibly useful tool for extracting primes from ANY size product and will do this extremely quickly.

this multiplication of 2 big prime numbers is an encoder isn't it ?

what will you do with that program once it's done ?

reply to post by ::.mika.::

what will you do with that program once it's done ?

Isn't it freaking obvious...destroy the worlds means of data encryption...making it obsolete...none of your data will be safe...mwahahaha...

EDIT: Spelling

EDIT: Hey...lets give it Garry Mckinnon...then he'd be able to get us the real good stuff that those Government agencies hide...

[edit on 28/10/09 by CHA0S]

reply to post by ::.mika.::

this multiplication of 2 big prime numbers is an encoder isn't it ?

Yes, you're right ... that's probably THE major use of prime numbers.

what will you do with that program once it's done ?

Donate it to the people of the world for the betterment of humanity

Originally posted by SpookyVince
An interesting point to notice though...

Everytime you reach one of your solutions (i.e. finding a and b so that for the 2 integer values of x the equation = 0), we can notice that the two roots (x1 and x2) multplied give b.

Similarly, we can notice that a is x1+x2...

Examples with your examples:
- a=225, b=3150 gives x1=15 and x2=210. x1*x2 = 15*210 = 3150, x1+x2 = 225
- starting with 23 and 1866, we have a=167 and b=1860, x1=12 and x2=155, and 12*155=1860 and 12+155 = 167

It seems to work everytime.

You're absolutely correct in that it does work everytime and well done for spotting it
Unfortunately, however ... the method you've picked up on has been known and used for ages to "guestimate" the roots of a quadratic equation.

Using the following as an example
[atsimg]http://files.abovetopsecret.com/images/member/57d784aee0cf.jpg[/atsimg]
you're basically looking for two numbers that when added together will give you 129 and that when multiplied together will give you 3154.
When you've found those two numbers, you will have found the "roots" for that particular quadratic equation.

As well as the above trial and error method of guestimating the two numbers, there's also the following well know equation that will spit out the roots for you:

[atsimg]http://files.abovetopsecret.com/images/member/d8a7461f589d.jpg[/atsimg]

reply to post by tauristercus


Yes indeed, those are well known methods, but I was just trying to find more or less efficient ways to go through it, as it will inevitably go for a complexity in the order of O(n²)... The point I was trying to reach is where, while still being a bad complexity, the number of iterations at each spot would be as low as possible.

I am not sure there are ways to do that work much more efficiently (i.e. log, linear or better even).

reply to post by tauristercus


Interesting. I noticed that but didn't know if it was actually generally true.

I guess a proof is thusly:

Consider a factored quadratic (a = 1):
(f*x + n)(g*x + m) = 0

The roots:
r1 = -n/f, -r1*f = n
r2 = -m/g, -r2*g = m

Multiply factors:
f*g*x^2 + n*g*x + m*f*x + n*m = 0

Substitute and simplify:
f*g*x^2 + f*g*(-r1 + -r2)*x + f*g*(-r1)*(-r2) = 0

a = f*g
b = -a*(r1 + r2)
c = a*r1*r2

Let a = 1
b = -(r1 + r2)
c = r1*r2

So I guess the rumors are true! I'm not sure having to search for the the roots to meet those criteria will reduce complexity.

Here is the best paper I could find on a quick algorithm to do what you are looking for. It doesn't need to be O(n^2) and in fact can be reduced to O(nlog^3n), making the calculations much faster.

www.computer.org...

This goes into a lot of discrete theory and algorithm analysis for finding the running times of these processes. As I said in my first post, I don't think you are going to be able to find a theorem or theory based calculation for finding these roots easily, and instead are going to be stuck in the realm of doing the calculation by simulation. This simulation will have a running time, and the running times can be anywhere from O(n^2) (very slow) to O(n), slow, but not as bad as n^2) or O(nlogn) much faster.

The algorithms in this paper are of the O(nlog^3n) variety, which means the algorithms are much faster than just doing the simulation linearly O(n).

Enjoy!

Originally posted by xmaddness
Here is the best paper I could find on a quick algorithm to do what you are looking for. It doesn't need to be O(n^2) and in fact can be reduced to O(nlog^3n), making the calculations much faster.

www.computer.org...

Thanks for locating that paper ... it made very interesting reading and even though I got the gist of what they were on about, I still have to admit that a large part of it went right over my head

Most of the research I've done (and this paper included), basically focus on extracting/processing roots from a single polynomial equation whereas I'm attempting to find a solution to an entirely different root determination problem.

Instead of concentrating on processing just a single quadratic equation in order to extract its roots, I'm using multiple quadratic equations that have been generated based on two staring numbers. Also instead of trying to obtain all roots from just a single quadratic equation, I need to determine which of the multiple quadratic equations that I generated is the ONLY one that produces INTEGER roots.

Here's another table example where I started with the initial two numbers of 4 and 4894.
Every table row entry is derived by subsequently adding a constant value of 24 to the preceding Value1 number and by subtracting a constant value of 1 from the preceding Value2 number.
The "new" Value1 and Value2 are then used to create the corresponding quadratic equation followed by root extraction.

[atsimg]http://files.abovetopsecret.com/images/member/5739c4fb3fd0.jpg[/atsimg]

As can be seen from the above table, an entire family of quadratic equations can be generated simply by supplying 2 initial starting values and subsequently performing a very simple addition and subtraction on these 2 values.

In fact, the entire quadratic equation family based on those 2 initial values can be calculated using the following simple equation and selecting suitable values of n from 0 to 15.

[atsimg]http://files.abovetopsecret.com/images/member/5c0ff92dac75.jpg[/atsimg]

Once again, to summarize ... given a set of quadratic equations derived from 2 initial starting values, how do I quickly AND efficiently determine which of the multiple equations is the ONLY one that produces integer roots ? Bear in mind that some initial starting values could generate a set of quadratic equations numbering in the 100's, 1000's or even millions and that I do NOT want to iterate through each of those quadratics and check its roots to see if they're integer only!
I need to hit the "bullseye" virtually immediately

Originally posted by tauristercus

I don't have a rigorous proof yet to conclusively state that "this process will always yield an integer value eventually" but I have run thousands of small scale tests using relatively small prime numbers to create the product ... and in each and every case, integer roots have ALWAYS been generated eventually.

Are you certain? If you're doing it via calculator or computer, you will ALWAYS run into buffer overflows which will cause it to round the number to only 10 decimal places.

...and you could always just do it in reverse; start from the answer and see what the equation comes out to be.

Originally posted by Byrd
...and you could always just do it in reverse; start from the answer and see what the equation comes out to be.

I had thought of that as well but he seems reluctant to explain exactly WHY he is picking coefficients in a particular way and so would it be valid for this purpose? If all were shared then perhaps some useful constraints would emerge.

reply to post by Byrd

Are you certain? If you're doing it via calculator or computer, you will ALWAYS run into buffer overflows which will cause it to round the number to only 10 decimal places.

A valid point but I'm using Mathematica and Maple for testing purposes which preserves accuracy to a great many decimal places ... so rounding is not an issue.

reply to post by EnlightenUp

I had thought of that as well but he seems reluctant to explain exactly WHY he is picking coefficients in a particular way and so would it be valid for this purpose? If all were shared then perhaps some useful constraints would emerge.

The only reason I'm reluctant to go into any detail as to how I arrive at the initial 2 starting values and why I use the constants 24 and 1 is because I've invested a great deal of time and effort in to this unique method that I have devised to "reverse engineer" any given product and extract the two original primes that were used.
I'm sure you'll appreciate I'm somewhat "possessive" (at least for the moment ) of my method and also of the effect this may potentially have on encryption systems that rely on primes.

If I can just overcome this final hurdle, then the method will be complete and I'll gladly disclose all.

reply to post by tauristercus


If roots are positive integers, then the sum must be less than the product except when one root is one, constraining the possibilities.

-b < c, unless one root =1

Any roots are < b

edit: fix brain reversal, not sure if I thought it out correctly anyway. An exception would be coefficients of -4 and 4.

Perhaps reverse generating polys from roots, given your starting values and the coefficient generator would let you easily check if the resulting equation fits the generator. Solving for n sould produce an integer if it fits on the "grid" for 24*n + b0 and c0 - n.

Now, I don't know if that helps. I'm tossing some more ideas out there.

[edit on 10/30/2009 by EnlightenUp]

[edit on 10/30/2009 by EnlightenUp]

[edit on 10/30/2009 by EnlightenUp]

I'm not familiar with the programs you mentioned, but this could be done very easily using Excel. That might be laughable compared to the programs you're using, and you wouldn't wanna go over a few thousand iterations but, nevertheless, it could be done in 15 minutes or so.