mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2013-01-31, 02:34   #1
literka
 
literka's Avatar
 
Mar 2010

C016 Posts
Default 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.
literka is offline   Reply With Quote
Old 2013-01-31, 08:19   #2
Gammatester
 
Gammatester's Avatar
 
Mar 2009

2·19 Posts
Default

Quote:
Originally Posted by literka View Post
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?
Gammatester is offline   Reply With Quote
Old 2013-01-31, 08:44   #3
literka
 
literka's Avatar
 
Mar 2010

26·3 Posts
Default

Quote:
Originally Posted by Gammatester View Post
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.
literka is offline   Reply With Quote
Old 2013-01-31, 08:58   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52×7×53 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2013-01-31, 09:44   #5
literka
 
literka's Avatar
 
Mar 2010

26·3 Posts
Default

Quote:
Originally Posted by LaurV View Post
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 is offline   Reply With Quote
Old 2013-03-07, 09:27   #6
literka
 
literka's Avatar
 
Mar 2010

110000002 Posts
Default

Quote:
Originally Posted by LaurV View Post
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?
literka is offline   Reply With Quote
Old 2013-03-07, 15:09   #7
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
Default

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
Raman is offline   Reply With Quote
Old 2013-03-07, 15:45   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

220738 Posts
Default

Quote:
Originally Posted by literka View Post
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...
LaurV is offline   Reply With Quote
Old 2013-03-09, 12:21   #9
literka
 
literka's Avatar
 
Mar 2010

26×3 Posts
Default

Quote:
Originally Posted by Raman View Post
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
literka is offline   Reply With Quote
Old 2013-03-09, 16:48   #10
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
Default

Quote:
Originally Posted by literka View Post
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)

Last fiddled with by Raman on 2013-03-09 at 16:50
Raman is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 20:16.

Mon Mar 8 20:16:40 UTC 2021 up 95 days, 16:27, 1 user, load averages: 1.87, 1.54, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.