mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2022-05-07, 23:34   #12
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·11·103 Posts
Default

You can always try to find the squares by trial and erfor. After all that is the Fermat’s factorization method. But:

Quote:

Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either.
https://en.wikipedia.org/wiki/Fermat...ization_method

For a formulaic solution to the problem, well it’s been a work in progress for centuries now. No proof that it can’t exist AFAIK.
a1call is offline   Reply With Quote
Old 2022-05-08, 02:26   #13
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×1,459 Posts
Default

Quote:
Originally Posted by Gelly View Post
Oh shoot my mistake! I'm sure I come off super foolish now that I remember what the particular context was. It seems like to get the sum of squares representation of any composite requires factorization, and I thought that was wrong because we know the sum of squares representation of C1133, the large composite factor of F12.
<snip>
A representation of a cofactor of a sum of two squares can be found by finding the representations of the known factors and dividing out.

I find this easiest to do using the complex factors a + b*I and a - b*I of a^2 + b^2. But it's a little tricky, because you have to choose the "correct" conjugate divisor of each prime factor. You only get one representation of the cofactor, of course.

The following is ridiculously clunky, but it gets the job done.
Code:
? {
v=[114689, 26017793, 63766529, 190274191361, 1256132134125569, 568630647535356955169033410940867804839360742060818433];
s2sq=Qfb(1,0,1);
w=vector(#v, i, qfbsolve(s2sq,v[i])*[1,I]~);
z=I+2^2048;
for(i=1,#w,if(gcd(w[i],z)==1,w[i]=conj(w[i])));
q=z/prod(i=1,#w,w[i]);
print(abs(real(q)));
print();
print(abs(imag(q)))
}
200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916

11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591
Dr Sardonicus is offline   Reply With Quote
Old 2022-05-19, 23:50   #14
bhelmes
 
bhelmes's Avatar
 
Mar 2016

24×52 Posts
Default

A peaceful and pleasant night for you,

if a compositon of n=x²+y² exists and n not a prime,
how many different compostions exist depending of the number of factors of n ?

Please have patience with me, I try to do progress in math and invite other to participate.


bhelmes is offline   Reply With Quote
Old 2022-05-20, 00:54   #15
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×1,459 Posts
Default

Quote:
Originally Posted by bhelmes View Post
<snip>
if a compositon of n=x²+y² exists and n not a prime,
how many different compostions exist depending of the number of factors of n ?
<snip>
  1. Drop the exclusion of primes.
  2. Say "representations" rather than "compositions".
  3. The meaning of "different" may be different from what you think it is.
Happy googling!
Dr Sardonicus is offline   Reply With Quote
Old 2022-06-04, 18:25   #16
bhelmes
 
bhelmes's Avatar
 
Mar 2016

40010 Posts
Default

A peaceful day for you,

Is there a known algorithm for
x²+y²=m²+n²=d mod f

I think it is easier than to find x²+y²=0 mod p

Any interesting suggestion how to speed up Gimps ?
I really need a new Mp.



Last fiddled with by bhelmes on 2022-06-04 at 18:36
bhelmes is offline   Reply With Quote
Old 2022-06-06, 12:38   #17
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×1,459 Posts
Default

Quote:
Originally Posted by bhelmes View Post
Is there a known algorithm for
x²+y²=m²+n²=d mod f
Let g = gcd(d, f).
  1. If g > 1 and any prime-power factor of g is congruent to 3 (mod 4) there is no solution.
  2. If g = 1, f is divisible by 4 and d == 3 (mod 4) there is no solution.
  3. If g = 1, f is divisible by 4, d == 1 (mod 4), r == 1 (mod 4), s == 1 (mod 4), and r*s == d (mod f) [e.g. r = d, s = 1], find primes p == r (mod f) and q == s (mod f). Then p*q provides a solution.

Last fiddled with by Dr Sardonicus on 2022-06-08 at 15:27 Reason: Strike out incorrect criterion
Dr Sardonicus is offline   Reply With Quote
Old 2022-06-08, 11:44   #18
bhelmes
 
bhelmes's Avatar
 
Mar 2016

24×52 Posts
Default

A peaceful and pleasant day for you,

I miss the case
4. g=1 and f odd

I am searching for x²+y²=m²+n²=d mod f, resp. two sums of squares with the same norm d mod f.

Algorithm:
choose a value r>0 and a start point x²+y²>f+r with x>y

if x²+y²>f+r then x:=x-1
if x²+y²<f then y:=y+1
if x²+y² > 0 mod f and x²+y² < r mod f store the pair with the norm and y:=y+1
if two points with the same norm is found stop the algorithm.

A visualisation and examples for small numbers can be found under
http://devalco.de/unit_circle/system_tangens.php

Is there a better algorithm available ?


bhelmes is offline   Reply With Quote
Old 2022-06-08, 16:10   #19
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·1,459 Posts
Default

I was completely wrong about the criterion for g > 1 with g = gcd(d, f). I struck it out.

As an example, x^2 + y^2 == 3 (mod 15) is solvable (e.g. x = y = 3). I had failed to consider that x^2 + y^2 could be divisible by a higher power of a prime than g, but the congruence (mod f) could still hold.

Mea culpa

A better approach is probably to factor the modulus f, and solve x^2 + y^2 == d (mod p) for each prime factor p of f. If f is divisible by a higher power of p, such solutions can be "lifted" to solutions mod p^2, etc.

If p is prime, one way to solve x^2 + y^2 == d (mod p) [assuming r is not 0 (mod p)] is by trial. Trying y = i = 0, 1, 2, etc. factor x^2 + i^2 - d (mod p). If it splits into linear factors, they give solutions to x^2 + i^2 == d (mod p). This should turn up a couple of solutions in fairly short order.

If d is 0 (mod p) there is always the solution x = y = 0 (mod p). If p = 2 there is the solution x = y = 1 (mod 2). If p is congruent to 1 (mod 4) there are several solutions.

Again, if f is divisible by a higher power of p, solutions mod p can be "lifted" to solutions mod p^2, p^3, etc.

Finally, solutions modulo the prime (power) factors of f can be combined using the Chinese Remainder Theorem.

Take d = 3, f = 15.

x^2 + y^2 == 3 (mod 3) [i.e. 0 mod 3] has the solution x = y = 0 (mod 3).

x^2 + y^2 = 3 (mod 5): Trying i = 0, no luck; i = 1, no luck. Trying i = 2, x^2 + 1 = 0 (mod 5) has the solutions x = 2 or 3 (mod 5).

Combining the mod 3 and mod 5 solutions we get 12^2 + 12^2, 3^2 + 12^2, and 3^2 + 3^2 == 3 (mod 15).

Last fiddled with by Dr Sardonicus on 2022-06-08 at 16:11
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 07:40.


Thu Jul 7 07:40:03 UTC 2022 up 2:27, 0 users, load averages: 1.01, 1.19, 1.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔