mersenneforum.org Remarks on Cornacchia's Theorem
 Register FAQ Search Today's Posts Mark Forums Read

 2013-01-31, 02:34 #1 literka     Mar 2010 26×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-01-31, 08:19   #2
Gammatester

Mar 2009

3810 Posts

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?

2013-01-31, 08:44   #3
literka

Mar 2010

26·3 Posts

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.

 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+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.
2013-01-31, 09:44   #5
literka

Mar 2010

26×3 Posts

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.

2013-03-07, 09:27   #6
literka

Mar 2010

26·3 Posts

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?

 2013-03-07, 15:09 #7 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 100111010012 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. (x1²+dy1²)(x2²+dy2²) = |x1x2+dy1y2|²+d|x1y2-y1x2|² = |x1x2-dy1y2|²+d|x1y2+y1x2|² (2x1²+dy1²)(2x2²+dy2²) = |2x1x2+dy1y2|²+2d|x1y2-y1x2|² = |2x1x2-dy1y2|²+2d|x1y2+y1x2|² 159 = 3 × 53 3 = 2x1² + 3y1², with x1 = 0, y1 = 1 53 = 2x2² + 3y2², with x2 = 5, y2² = 1 (2x1²+dy1²)(2x2²+dy2²) = |2x1x2+dy1y2|²+2d|x1y2-y1x2|² = |2x1x2-dy1y2|²+2d|x1y2+y1x2|² 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
2013-03-07, 15:45   #8
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

26E916 Posts

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

2013-03-09, 12:21   #9
literka

Mar 2010

26×3 Posts

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.

Last fiddled with by literka on 2013-03-09 at 12:22

2013-03-09, 16:48   #10
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

100111010012 Posts

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 \\
(q,\ r)\ =\ (r\ mod\ q,\ q) \\
\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)

Last fiddled with by Raman on 2013-03-09 at 16:50

 Similar Threads Thread Thread Starter Forum Replies Last Post bgbeuning Computer Science & Computational Number Theory 7 2015-10-13 13:55 henryzz Math 2 2012-05-06 13:01 wpolly Math 3 2008-11-12 12:31 herege Math 25 2006-11-18 09:54 grandpascorpion Factoring 0 2006-09-10 04:59

All times are UTC. The time now is 18:36.

Thu May 19 18:36:17 UTC 2022 up 35 days, 16:37, 1 user, load averages: 0.85, 0.96, 1.11