Translate

Monday, October 20, 2014

General binary quadratic Diophantine solution algorithm?

Even if I'm not sure it works, it's worth it for me to put forward the ideas for what might be a general solution algorithm for binary quadratic Diophantine equations just in case it does work.

Coming up with a general solution algorithm would complete my research in this area, as I already have a general method for reducing. For me the idea of a complete theory is enticing.

A complete theory of binary quadratic Diophantine equations would be a boon to research.

The reduced form for binary quadratic Diophantine equations x2 - Dy2 = F can be easily solved modularly to give:

y2 = (x2 - F)/D mod N

where x is some residue modulo N. If x and y have explicit solutions there must be some x mod N, for which (x2 - F)/D will be a quadratic residue. And it is possible to probe more deeply with a slightly more complex solution to get more information about what is happening internally, and also reveal an additional constraint.

It can be shown that x2 - Dy2 = F can also be solved modularly to give:

y2 = (r2 - 2mr)/D mod N, x = r + (Dy2)/(2r) mod N

Where N can be any integer for which F is a quadratic residue, where: m2 = F mod N, and r is a residue modulo N, for which y exists.

This result is found by the modular factorization:

x2 - F = Dy2  = (x - m)(x + m) mod N

by considering r, a residue of N, where: x+m = r, and x-m = (Dy2)/r


Proof:

Given x2 - Dy2 = F, consider N such that F is a quadratic residue modulo N, so there must exist m such that m2 = F mod N.

Then we have trivially: x2 - F = x2 - m2 = (x - m)(x + m) mod N

Now consider r modulo N, such that:

x2 - F = r[(Dy2)/r] = (x + m)(x - m) mod N

The existence of r is a result of F being a quadratic residue of N, as only then must there exist at least two residues modulo N that give Dy2 mod N as their product, if solutions exist.

Let: x+m = r mod N, and x-m = (Dy2)/r mod N

Solving gives:

2x = r + (Dy2)/r mod N and 2m = r - (Dy2)/r mod N

And using the second I can solve for y2:

y2 = (r2 - 2mr)/D mod N

So I have finally:

y2 = (r2 - 2mr)/D mod N, x = r + (Dy2)/(2r) mod N

Proof complete.

Notice that r = 2m mod N, will always give x = m mod N and y = 0 mod N, so it is not giving unique information, which is also true for r = -2m mod N. However, if explicit solutions do exist and there are no other solutions it means y = 0 mod N. If it's not already known that explicit solutions must exist, no other solutions except the default one may mean no explicit solutions exist.

This result shows that N being made up of primes for which F is a quadratic residue is mathematically significant, as it increases the complexity, with the existence of r.

The existence of r and the requirement that (r2 - 2mr)/D be a quadratic residue of N gives constraints which may highlight explicit solutions because they have a 100%  probability of giving an r, if they exist, which suggests a rather basic modular solution algorithm.

Modular algorithm:

Collect a list of primes p for which F is a quadratic residue. That should be the case for at least 50% of primes or for all primes if F is a square. The needed size of that list will depend on the size of x and y necessary to factor. The primorial gives roughly the size of solution that can be handled by any particular number of primes in the list.

Given two primes p1 and p2 on that list, Let N equal the product of the two primes, and calculate y and x, which may have multiple solutions. There will be two values for m and you need to use both! While there may be two distinct solutions for y for any particular r that works, as you're solving a quadratic residue to get it, you only need one, as modulo each prime they only vary by sign.

Discard values where r = 2m or -2m mod N, as those always exist and give no useful information, unless you know there must exist explicit solutions and no other values give solutions. In that case then you know y = 0 mod N is forced. For other cases where y2 = 0 mod N verify that calculated x and y = 0 mod N actually work with x2 - Dy2 = F mod N. Discard any cases where they do not.

Solutions can vary only by sign, where you need a consistent way of handling sign variations.

For example: 5 mod 10 and 10 mod 5 only vary by sign as 10 mod 5 is -5 mod 15. You don't necessarily want to look at those as different solutions since both x and y are squared in the root equation. You might always just take the smaller, so check to see if you have a negation.

There must be solutions if the explicit equation has solutions. If you find no solutions, except the default case, for any prime p for which F is a quadratic residue then there may be no solutions to the explicit equation. But you don't know for sure with just a single case.

Save possible x and y modular values, increment the count for a solution residue by prime.

For example, with N = p1p2, you have x mod p1p2, but would save x mod p1 and x mod p2, so you save by prime.

Save linked prime and its residue for a particular prime if the other prime is the next smallest prime, assuming your list goes from smallest prime to greatest. That way each prime is linked to only one other.

Repeat with each combination of your list of primes by 2, and keep a hit count for each factor modulo a particular prime.

After you have completed looping through all prime combinations by two, and stored values by prime, incrementing the counts of particular residues by prime as they are verified, you should have resonance spikes around values that come from the explicit solutions.

That is, the values with the highest counts should be values from the explicit solutions.

If there are no spikes then you have a growing probability that no explicit solution exists. As the alternative is that every explicit solution for y has each of your primes as a factor.

If you do have resonance spikes, solve for the explicit x and y using the solutions at each prime, which is of course easy, as for instance you could use the Chinese Remainder Theorem. If you have multiple factors you can use linked primes to tell which  go with each other.

I'll use a small example to show some numbers without demonstrating the full algorithm as described above.

Let D = 4, F = -119. I need it negative as I need F mod 4 = 1 for an explicit solution. I note that 3 and 5 are primes that will work, so will take them as a pair with N = 15.

As m2 = F mod N = -119 mod 15 = 1 mod 15, m = 1 mod 15 is a solution. And m = 11 mod 15 is another. Will first use m = 1 mod 15.

So: y2 = 4(r2 - 2r) mod 15

And: x = r + (4y2)/(2r) mod 15

The quadratic residues of 15 are: 1, 4, 6, 9, 10

We find that r = 2, gives 0, and works, but no other values work except:

r = 6 and r = 11, where both give y2 = 6 mod 15, which has y = 6 mod 15 as a solution, and is a non-trivial case.

Solving for x with the first: 2x = 6 + (4(6))/6 mod 15 = 6+4 mod 15 = 10 mod 15, so x = 5 mod 15.

With the second you get 2x = 11 + (4(6))/11 mod 15 = 11 + 9 = 20 mod 15, so x = 10 mod 15, which is of course -5 mod 15.

And x = 5 mod 15 and y = 6 mod 15 work.

And x = 5, and y = 6 work explicitly, which is why it's a small example for basic demonstration purposes.

Now using m = 11 mod 15.

So: y2 = 4(r2 - 22r) mod 15 = = 4(r2 - 7r) mod 15

And: x = r + (4y2)/(2r) mod 15

And r = 7 works, to give x = 11 mod 15 and y = 0 mod 15. That gives 11(11) = 121 which is larger than 119, so beyond interest here.

So why might this thing work where other modular approaches have failed?

Well that limiting quadratic residues is a BIG DEAL.

There is a 100% certainty of a quadratic residue for an r for an explicit solution, but for others the likelihood should be less! Which means you can simply look at counts by r, with resonance spikes around the explicit solutions.

That I could bring in the concept of resonance was really exciting.

Actually running the algorithm could look like watching a spectrometer as peaks built around the explicit solutions while other values had lesser heights. Kind of wonder what it would look like exactly. Would there be lesser mounds or just sharp spikes surrounded by a few odd counts randomly distributed? If it works...

So why really? Well now with x + m = r and x - m = (Dy2)/r, you're balancing the variable x against the constant m, which is the kind of thing that has come up in my research before, so it was eery here to see it valuable again. That gives very little wiggle room. The math has to figure out all kinds of things to make it work! Which means it's hard for me to comprehend the complexity. But it means some values for r are not available, as both x+m and x-m can't behave as needed.

Of course if it DOES resolve by prime then building the full factor is easy. There are a couple of techniques including the Chinese Remainder Theorem, but I like one I found on my own and then discovered was not new.

For instance 7 = 1 mod 3 and and 7 =  2 mod 5.

Using the formula gives it right back: 1 + 3(2) mod 15 = 7 mod 15

So 1 mod 3 and 2 mod 5 give you 7.

The ability to describe a number with its residues by prime is kind of cool. So yeah, if you have the prime residues then you have the number, where you need fewer primes than the closest value of the primorial to your number. And the primorial rises faster than the factorial!


James Harris

Friday, October 17, 2014

Modular integer factorization algorithm

The general reduced form of the binary quadratic Diophantine equation x2 - Dy2 = F can be solved modularly to give:

y2 = (r2 - 2m'r)/D mod N'

2x = r + (Dy2)/r mod N'

Where N' is any integer for which F is a quadratic residue, where: m'2 = F mod N'

This result is found by the modular factorization:

x2 - F = Dy2  = (x - m')(x + m') mod N'

by considering r, a residue of N', where: x+m' = r, and x-m' = (Dy2)/r

That (r2 - 2m'r)/D must be a quadratic residue of N gives a constraint which can be used for a modular integer factorization algorithm.

Modular algorithm:

Let D = 4. Then x2 - 4y2 = F, will have solutions for any odd F, as long as F = 1 mod 4. So F is positive or negative as every odd integer is either 1 or -1 mod 4.

And of course we have a factorization with: (x-2y)(x+2y) = F.

Then collect a list of primes p for which F is a quadratic residue. That should be the case for roughly 50% of primes. The needed size of that list will depend on the size of x and y necessary to factor. The primorial gives roughly the size of the factor that can be handled by any particular number of primes in the list.

Given two primes p1 and p2 on that list, Let N' equal the product of the two primes, and calculate y and x, which may have multiple solutions. There will be two values for m' and you need to use both! While y will tend to have two distinct solutions for each r that works, they differ by each prime only by sign, so you only need to use one.

Discard values where r = 2m' or -2m' mod N', as those always exist and give no useful information, and cover the trivial factorizations, unless there are no other solutions, as then y = 0 mod N is forced. For other cases where y2 = 0 mod N' verify that x and y calculated actually work with x2 - 4y2 = F mod N'. Discard any cases where they do not.

Use your x and y to find the factors mod N'. The two factors are (x-2y) and (x+2y).

For example, f1 = x - 2y mod N', and f2 = x+2y mod N' is an option.

There must be solutions since the explicit equation has solutions. But this approach automatically leaves off the trivial factorization. If no other solutions besides the trivial factorization, represented by r = 2m' or -2m mod N', exist then F must be a prime number.

Save possible factors by prime, so for instance if you have f1 mod p1p2 you'd take f1 mod p1 and store it, and then f1 mod p2 and store it, and increment the count for each factor residue by prime.

Save linked prime for each if it is less than the larger prime, assuming you go from smaller primes to greater in your list or vice versa otherwise. That way you save only one linked prime per prime.

Repeat with each combination of your list of primes by 2, and keep a hit count for each factor modulo a particular prime. You can optionally store x and y as well, but shouldn't need them.

Values that are the same across both primes have the highest probability of coming from the explicit solutions as they must always exist.

After you have completed looping through all prime combinations by two, and stored values by prime incrementing the counts as they are verified, you should have resonance spikes around values that come from the explicit solutions.

That is, the values with the highest counts should be values from the explicit solutions.

Now solve for the explicit factors using the solutions at each prime, which is of course easy, as for instance you could use the Chinese Remainder Theorem. If you have multiple factors you can use linked primes to tell which factors go with each other.

I'll use a small example to show some numbers without demonstrating the full algorithm as described above.

Let F = -119. I need it negative as I need F mod 4 = 1. I note that 3 and 5 are primes that will work, so will take them as a pair with N' = 15.

As m'2 = F mod N' = -119 mod 15 = 1 mod 15, m' = 1 mod 15 is one solution, while m' = 11 mod 15 is the other. Using m' = 1 mod 15 first.

So: y2 = 4(r2 - 2r) mod 15

And: 2x = r + (4y2)/r mod 15

The quadratic residues of 15 are: 1, 4, 6, 9, 10

We find that r = 2, gives 0, and works, but no other values work except:

r = 6 and r = 11, both give y2 = 6 mod 15, which has y = 6 mod 15 as a solution, and is a non-trivial case.

Solving for x with the first: 2x = 6 + (4(6))/6 mod 15 = 6+4 mod 15 = 10 mod 15, so x = 5 mod 15.

And r = 11, gives x = 10 mod 15, which of course is -5 mod 15.

So x = 5 mod 15 and y = 6 mod 15 are solutions.

And x = 5 and y = 6 work explicitly, which is why it's a small example for basic demonstration purposes. In general of course the factor can be much larger than the primes being used.

x2 - 4y2 = -119 = (x+2y)(x-2y) = (5 + 2*6)(5 - 2*6) = (17)(-7)

The other case is m' = 11 mod 15.

So: y2 = 4(r2 - 22r) mod 15 = 4(r2 - 7r) mod 15

And: 2x = r + (4y2)/r mod 15

And r = 7 mod 15 works, to give x = 11 mod 15, and y = 0 mod 15. This case is removed though because 11(11) = 121, which is larger than 119.

If you were using the algorithm you would increment the count for 2 mod 3, and for 2 mod 5, for one factor, and increment 2 mod 3 for the second and 3 mod 5 for the second.

So for factor one, 0 mod 3, and 1 mod 3 would have zero hits, while 2 mod 3 would have one hit, and 2 mod 5 would have one hit, while all other residues and 0 mod 5 would have zero hits. And for factor two, 2 mod 3 would be the only one with a hit modulo 3, while 3 mod 5 would be the only one modulo 5.

The linked prime for 2 mod 3 would be 5 with the solution 2 mod 5.

You only need to link one way, so conversely could link 2 mod 5 to 3 with the solution 2 mod 3. And probably only need one link, so might choose the next closest prime, either larger or smaller.

Linking primes allows you to distinguish multiple factorizations. Information would be unnecessary if there are only two prime factors, as in the example.


James Harris

Wednesday, October 08, 2014

Example showing truth, logic and absolute proof

Thought I would talk out a simple example showing absolute proof with a basic mathematical argument, from beginning with a truth, to logical steps, to a conclusion which must be true. So I'll give a lot of detail.

This example will prove that if x2 + y2 = z2 then (v2 - 1)z2 - 2xy = 0(mod x+y+vz), where v can be any value.

Step one: Start with a truth

1. x+y+vz = x+y+vz

A lof of my research begins with an identity, which of course is true. For me a truth is something that does not change. Which means it must be true no matter what.

Proceed using logical steps, where some might prefer to say, valid mathematical steps.

2. x+y+vz = 0(mod x+y+vz)

(If "mod" is unfamiliar to you or you have questions about my usage of it, please check out this post.)

That simply states that x+y+vz has itself as a factor, and is actually a truth from which one could start, but I like to begin with the explicit identity, when I'm explaining in a lot of detail.

3. x+y = -vz (mod x+y+v)

Subtracted vz mod x+y+vz from both sides.

4. x2 + 2xy + y2 = v2z2 (mod x+y+vz)

Here I've just continued with basic algebra, squaring both sides. If you're worried you can do it all explicitly. Now it's time to introduce what I call a conditional.

5. Let x2 + y2 = z2 and subtract from 4.

It is, unlike the identity with which we started, not always true. So now things remain true under certain conditions.

6. 2xy = (v2 - 1)z2 (mod x+y+vz)

Simplifying a bit, more for presentation.

7. (v2 - 1)z2 - 2xy = 0(mod x+y+vz)

Proof complete.

This type of result is true with the condition that x2 + y2 = z2, so it's like, if that is true then

(v2 - 1)z2 - 2xy = 0(mod x+y+vz) must be true.

That conditional result is what I call a conditional residue.

This simple example shows how you begin with a truth, and connect truth to truth, as well as use a conditional to find what must be true when that condition is met.

Notice v is a perfectly independent variable.

As long as x, y and z fit the conditional, for instance, x = 3, y = 4, z = 5, then v can take any value.

For example: (v2 - 1)25 - 2(3)(4) = 0(mod 3+4+5v)

Which is just: 25v2 - 49 = 0(mod 5v + 7), which can be seen to be true by inspection.

For a second example, let v=1, then you have -2xy = 0(mod x+y+z) is true if x2 + y2 = z2.

With our values: -2(3)(4) = 0( mod 3+4+5), which is -24 = 0 mod 12

So now you know that if x2 + y2 = zthen 2xy has x+y+z as a factor.

As v is completely free there are an infinity of such relations available. Notice you can also probe behavior of x, y and z by what v you pick, so it can be an analysis tool.

The conditional residue contains all information about the conditional itself, which allows you to probe behavior of the conditional through it.

The purpose of this post is to step through showing a truth, logical steps, which are also valid mathematical steps, to get to a conclusion which must be true.

Once you understand the basics, you can handle far more complex examples and understand why you have absolute proof without any possibility of doubt.

Each of the steps above, is both logical, and a valid mathematical step. I call those steps, linkages.

For example, the linkage from x+y+vz = 0(mod x+y+vz) to x+y = -vz(mod x+y+vz), is the logical step of subtracting vz mod x+y+vz from both sides. Notice that is a valid mathematical step.

One of those things I rarely do with my own arguments is state when a proof is complete, but do so at times when explaining in detail.

You may notice that the argument was perfect at each step.

Correct mathematical arguments have the property of being correct at each step.


James Harris