mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-08-25, 07:32   #1
SPWorley
 
Jul 2009

31 Posts
Default Breaking a prime p into a^2 + 3* b^2

I'm playing with cubic reciprocity formulas.

From that link, it states "A theorem of Fermat states that every prime p ≡ 1 (mod 3) is the sum of a square and three times a square: p = a^2 + 3b^2"

How would you go about finding a and b given p?

Is there a better strategy than brute force, iterating b=1, b=2, b=3, b=4.. etc and seeing if the remainder (p-3*b^2) is a square?
There are efficient square-detecting routines, but even if they're cheap, you could be iterating up to sqrt(p) times!

How about the case where p=a^2 +2* b^2, which comes up when dealing with quartic reciprocity?

Last fiddled with by SPWorley on 2009-08-25 at 07:32
SPWorley is offline   Reply With Quote
Old 2009-08-25, 09:46   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by SPWorley View Post
I'm playing with cubic reciprocity formulas.

From that link, it states "A theorem of Fermat states that every prime p ≡ 1 (mod 3) is the sum of a square and three times a square: p = a^2 + 3b^2"

How would you go about finding a and b given p?

]

Factor p over Q(sqrt(-3)). See H. Cohen's book on Algebraic Number Theory.
I believe that a variation of Cornachia'a algorithm is used, but my memory
could be faulty. It's been a long time since I looked at this kind of stuff.
R.D. Silverman is offline   Reply With Quote
Old 2009-08-25, 12:08   #3
Gammatester
 
Gammatester's Avatar
 
Mar 2009

468 Posts
Default

Quote:
Originally Posted by SPWorley View Post
How about the case where p=a^2 +2* b^2, which comes up when dealing with quartic reciprocity?
Cornacchia's algorithm can be used in this case too, generally you can solve a^2 + d*b^2 = p, with 0<d<p. There is a modified algorithm for a^2 + |d|*b^2 = 4p. Crandall/Pomerance: Prime Numbers (Algorithm 2.3.12 +) is another reference.
Gammatester is offline   Reply With Quote
Old 2009-08-26, 03:05   #4
SPWorley
 
Jul 2009

111112 Posts
Default

Thanks very much for the references.. it's all there in Crandall/Pomerance.

Pretty straightforward, too!

I appreciate it.
SPWorley is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Grammar rule-breaking ftw jasong Lounge 71 2013-10-15 03:39
Breaking: US DOJ Spied for Months on AP Reporters ewmayer Soap Box 11 2013-06-06 06:15
disk died, prime work lost forever? where to put prime? on SSD or HDD? emily PrimeNet 3 2013-03-01 05:49
Breaking up files roger Information & Answers 13 2007-11-17 06:50
Beowolf cluster on the Cheap, breaking 100$/GFlop jflin Hardware 8 2007-09-06 08:25

All times are UTC. The time now is 08:30.


Sat May 28 08:30:40 UTC 2022 up 44 days, 6:31, 0 users, load averages: 1.15, 1.27, 1.42

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.

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