Remarks on Cornacchia's Theorem

literka · 2013-01-31, 02:34

Recently I wrote a new page http://www.literka.addr.com/mathcoun...cornacchia.htm I hope it gives a new approach for Cornacchia's algorithm. Proofs of Cornacchia's I saw before were unreadable and complicated. Proof I presented is, in my opinion, straightforward. My approach avoids computing square roots, as it is in original Cornacchia's algorithm.

Gammatester · 2013-01-31, 08:19

Quote:

Originally Posted by literka

My approach avoids computing square roots, as it is in original Cornacchia's algorithm.

How do you get the starting value r1 := r with r^2 = -1 mod m without taking square roots mod m?

literka · 2013-01-31, 08:44

Quote:

Originally Posted by Gammatester

How do you get the starting value r1 := r with r^2 = -1 mod m without taking square roots mod m?

It is assumption. Assumptions are the same as in Cornacchia's algorithm.

LaurV · 2013-01-31, 08:58

Also, how do you "easy generalize" for d>1? If d>1 your theorem does not hold. Example: x^2+6*y^2=159, there is no r for which r^2=-1 (mod 159), because 159=3 (mod 4) and -1 is quadratic residue only when m=1 (mod 4). Therfore, according with your demonstration, there should be no solution for the given equation. OTOH, it is easy to see that 3^2+6*5^2=159.

literka · 2013-01-31, 09:44

Quote:

Originally Posted by LaurV

Also, how do you "easy generalize" for d>1? If d>1 your theorem does not hold. Example: x^2+6*y^2=159, there is no r for which r^2=-1 (mod 159), because 159=3 (mod 4) and -1 is quadratic residue only when m=1 (mod 4). Therfore, according with your demonstration, there should be no solution for the given equation. OTOH, it is easy to see that 3^2+6*5^2=159.

I thought very little about case d>1. The case d=1 was always most important for me. At the current time, I don't have ready theorem for d>1. I didn't write that theorem will look the same way for d>1. In fact I did not write anything for this case. Whole page is about the case d=1.
This corresponds also to a second part of your post. Your counterexample
3^2+6*5^2=159
evidently is for the case d=6. The part of Theorem about non-existence of solution is taking live from Cornacchia's theorem. I don't prove it on my page, since it was proved a century ago. I proved only a part, which looked new (at least for me). I had ready some remarks concerning non-existence. But I did not write it, since it was 4 in the night and I wanted this page to be off my head. For sure, I will update this page.

literka · 2013-03-07, 09:27

Quote:

Originally Posted by LaurV

Also, how do you "easy generalize" for d>1? If d>1 your theorem does not hold. Example: x^2+6*y^2=159, there is no r for which r^2=-1 (mod 159), because 159=3 (mod 4) and -1 is quadratic residue only when m=1 (mod 4). Therfore, according with your demonstration, there should be no solution for the given equation. OTOH, it is easy to see that 3^2+6*5^2=159.

After reading your post for the second time I realized that your post is a nonsense. I wrote about the case when solution r^2=-1 (mod n) exists. It is an assumption of Theorem and I did not write anything about the case when it does not exist.
Moreover, it is Cornacchia's theorem, which was not denied (except of you) for more than century. I made only some remarks.
Moreover, you wrote about theorem, but you say "according to your demonstration" not "according to your theorem".
Moreover, 3^2+6*5^2=159 is a solution for something, but does not correspond to what I wrote. I considered only equations of the form a^2+b^2=m (mod n).
Moreover, my remarks can be easily generalized for d>1, But I leave it to readers to do this. Generalized theorem does not have to look exactly the same as original.
Have you ever taken math courses?

Raman · 2013-03-07, 15:09

For d > 1, you do start with r² = -d (mod m), but do not start with r² = -1 (mod m).

Then, x = Real Part of GCD(m, r+√-d)
Then, y = Imaginary Part of GCD(m, r+√-d)

if a solution does exist to x²+dy² = m.

The Cornacchia's algorithm works out actually for the prime values of m only.

For the composite values of m, you must combine the prime factors together by using the
underlying representable quadratic form polynomials of the same discriminant value of -4d,
by making for using the following identity / other equations, etc.

(x₁²+dy₁²)(x₂²+dy₂²) = |x₁x₂+dy₁y₂|²+d|x₁y₂-y₁x₂|² = |x₁x₂-dy₁y₂|²+d|x₁y₂+y₁x₂|²
(2x₁²+dy₁²)(2x₂²+dy₂²) = |2x₁x₂+dy₁y₂|²+2d|x₁y₂-y₁x₂|² = |2x₁x₂-dy₁y₂|²+2d|x₁y₂+y₁x₂|²

159 = 3 × 53
3 = 2x₁² + 3y₁², with x₁ = 0, y₁ = 1
53 = 2x₂² + 3y₂², with x₂ = 5, y₂² = 1

(2x₁²+dy₁²)(2x₂²+dy₂²) = |2x₁x₂+dy₁y₂|²+2d|x₁y₂-y₁x₂|² = |2x₁x₂-dy₁y₂|²+2d|x₁y₂+y₁x₂|²

159 = 3² + 6 × 5²

Or if -d is being a quadratic non-residue mod m, or if p² | m, then
if m/p² = a²+db² then certainly that
m = (pa)²+d(pb)²; m = x² + dy² form with x = pa, y = pb.

@ literka : You may wish to experiment your own algorithm / implementation
with the following twenty-six values A-Z, Cases of prime numbers that are being congruent
to {1, 9, 15, 23, 25, 39} mod 56, if in case
whether they are being of following form x²+14y², or 2x²+7y².

as since 14 is not being an ideonal / or aka convenient number, from among within it, into them, its their own place, position respectively

LaurV · 2013-03-07, 15:45

Quote:

Originally Posted by literka

Have you ever taken math courses?

I tried few times, but the bookstore keepers caught me every time. I don't know how the hack they do...

literka · 2013-03-09, 12:21

Quote:

Originally Posted by Raman

The Cornacchia's algorithm works out actually for the prime values of m only.

Cornacchia's algorithm works not only for m prime only. I quote from Wikipedia:

"In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation , where and d and m are coprime."

However I understand your position that finding solutions for prime factors gives a solution for m.
What surprises me that in Cornacchia's algorithm there appear square roots. Square roots are hard to compute (I mean they take lot of time to compute). My remarks show that it can be avoided.

BTW. I read few last your posts. There are few things things which surprise me. But I am in the middle of something different (and it is not Cornacchia's theorem). May be I will write soon, but in your thread.

Raman · 2013-03-09, 16:48

Quote:

Originally Posted by literka

Cornacchia's algorithm works not only for m prime only. I quote from Wikipedia:

"In computational number theory, Cornacchia's algorithm is an algorithm for solving the Diophantine equation , where and d and m are coprime."

Yes, that is right!

But, that for finding out the square roots modulo composite numbers... there is being no straightforward method...
you have to find out for the individual prime factors by using Tonelli-Shanks algorithm...
and then combine them product put altogether, by using Chinese Remainder Theorem...

If in case whether there does exist N solutions to x²+dy² = m,
then there must be 2*N square roots of -d modulo m, between 1 & m-1.

Try solving out following equation
x² + 24y² = 385.

Each & every square root r of -24 mod 385, along with its own twin complement 385 - r,
yields out a single different solution into following above mentioned equation...
^{[SUP][SUP][SUP][SUP][SUP][COLOR=White]by using it that this some same way... it into them... they of r for the...[/COLOR]}[/SUP][/SUP][/SUP][/SUP][/SUP]

By finding out square roots for composite numbers, by using them,
before taking out GCD of m with r+√-d into field Z[√-d]
is being quite directly equivalent to the step stage alone of combining individually prime factor products
by using them as that this way

(s²+dt²)(u²+dv2²) = |su+dtv|²+d|sv-tu|² = |su-dtv|²+d|sv+tu|²
(2s²+dt²)(2u²+dv²) = |2su+dtv|²+2d|sv-tu|² = |2su-dtv|²+2d|sv+tu|²

right afterwards after taking out GCD of m with r+√-d into field Z[√-d]

by using them, finding out taking out square roots for composite numbers

$r^2\ =\ -d\ (mod\ \prod_{i=1}^{n}p_i)$

$Let$
$w_k^2\ =\ -d\ (mod\ p_k)$
$k\ =\ 1..n$

$by\ using\ them,\ Chinese\ Remainder\ Theorem...$

$u_k\ =\ \frac{\prod_{i=1}^{n}p_i}{p_k}$
$v_k\ =\ (u_k\ mod\ p_k)^{-1}\ mod\ p_k$
$k\ =\ 1..n$

$r\ =\ \sum_{i=1}^{n}u_iv_iw_i\ mod\ \prod_{i=1}^{n}p_i$

and then , applying , over thereby , by using them , Cornacchia-Smith algorithm , step stage alone^{[SUP][SUP][SUP][SUP][SUP]

[COLOR=White]it that this it into them... they of r for the... being from among within into for the

of r the it into them, within , into into be being that own way , this own process , it into them , within , into into[/COLOR]}[/SUP][/SUP][/SUP][/SUP][/SUP]
$The\ Cornacchia-Smith\ algorithm\ works\ out\ as\ follows,\ following$

$a^2 + kb^2 = p$

$q\ =\ \sqrt{-k}\ (mod\ p)$
$r\ =\ p$

$while(q^2 \ge p)$
$\lbrace \\<br /> (q,\ r)\ =\ (r\ mod\ q,\ q) \\<br /> \rbrace$

$(a, b)\ =\ (q, \sqrt{\frac{p-q^2}{k}})$
$if\ \sqrt{\frac{p-q^2}{k}}\ is\ an\ integer.$

$And\ then\ for\ solving\ the\ equation$
^{[SUP][SUP][SUP][SUP][SUP]

[COLOR=White]so, thus?

thus, why so, thus?[/COLOR]}[/SUP][/SUP][/SUP][/SUP][/SUP]
r² = -d (mod m)
^{[SUP][SUP][SUP][SUP][SUP]

[COLOR=White]for the

of r the[/COLOR]}[/SUP][/SUP][/SUP][/SUP][/SUP]GCD(m, r+√-d)

2013-01-31, 02:34	#1
literka Mar 2010 2⁶×3 Posts	Remarks on Cornacchia's Theorem Recently I wrote a new page http://www.literka.addr.com/mathcoun...cornacchia.htm I hope it gives a new approach for Cornacchia's algorithm. Proofs of Cornacchia's I saw before were unreadable and complicated. Proof I presented is, in my opinion, straightforward. My approach avoids computing square roots, as it is in original Cornacchia's algorithm.

2013-03-07, 15:09	#7
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 10011101001₂ Posts	For d > 1, you do start with r² = -d (mod m), but do not start with r² = -1 (mod m). Then, x = Real Part of GCD(m, r+√-d) Then, y = Imaginary Part of GCD(m, r+√-d) if a solution does exist to x²+dy² = m. The Cornacchia's algorithm works out actually for the prime values of m only. For the composite values of m, you must combine the prime factors together by using the underlying representable quadratic form polynomials of the same discriminant value of -4d, by making for using the following identity / other equations, etc. (x₁²+dy₁²)(x₂²+dy₂²) = \|x₁x₂+dy₁y₂\|²+d\|x₁y₂-y₁x₂\|² = \|x₁x₂-dy₁y₂\|²+d\|x₁y₂+y₁x₂\|² (2x₁²+dy₁²)(2x₂²+dy₂²) = \|2x₁x₂+dy₁y₂\|²+2d\|x₁y₂-y₁x₂\|² = \|2x₁x₂-dy₁y₂\|²+2d\|x₁y₂+y₁x₂\|² 159 = 3 × 53 3 = 2x₁² + 3y₁², with x₁ = 0, y₁ = 1 53 = 2x₂² + 3y₂², with x₂ = 5, y₂² = 1 (2x₁²+dy₁²)(2x₂²+dy₂²) = \|2x₁x₂+dy₁y₂\|²+2d\|x₁y₂-y₁x₂\|² = \|2x₁x₂-dy₁y₂\|²+2d\|x₁y₂+y₁x₂\|² 159 = 3² + 6 × 5² Or if -d is being a quadratic non-residue mod m, or if p² \| m, then if m/p² = a²+db² then certainly that m = (pa)²+d(pb)²; m = x² + dy² form with x = pa, y = pb. @ literka : You may wish to experiment your own algorithm / implementation with the following twenty-six values A-Z, Cases of prime numbers that are being congruent to {1, 9, 15, 23, 25, 39} mod 56, if in case whether they are being of following form x²+14y², or 2x²+7y². as since 14 is not being an ideonal / or aka convenient number, from among within it, into them, its their own place, position respectively Last fiddled with by Raman on 2013-03-07 at 15:17

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Pocklington's Theorem	bgbeuning	Computer Science & Computational Number Theory	7	2015-10-13 13:55
Modified Cornacchia-Smith Algorithm	henryzz	Math	2	2012-05-06 13:01
Koebe's 1/4 Theorem	wpolly	Math	3	2008-11-12 12:31
Number Theorem	herege	Math	25	2006-11-18 09:54
Størmer's theorem	grandpascorpion	Factoring	0	2006-09-10 04:59

2013-01-31, 08:58	#4
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 7·1,423 Posts	Also, how do you "easy generalize" for d>1? If d>1 your theorem does not hold. Example: x^2+6y^2=159, there is no r for which r^2=-1 (mod 159), because 159=3 (mod 4) and -1 is quadratic residue only when m=1 (mod 4). Therfore, according with your demonstration, there should be no solution for the given equation. OTOH, it is easy to see that 3^2+65^2=159.